Cod sursă (job #786177)

///varianta fara AIB-75pct

#include <iostream>
#include <fstream>
using namespace std;

ifstream f("dejavu.in");
ofstream g("dejavu.out");

const int NMAX = 5004;
const int MOD = 1000000007;

int dp[NMAX][NMAX / 2];
int v[NMAX], fr[NMAX];

int n, Q;

void calc_prefix()
{
    for(int i = 0; i <= n; i++)
        dp[n][i] = 1;

    for(int k = n - 1; k >= 0; k--)
        for(int p = 0; p * 2 <= k ; p++)

        {
            int q = k - 2 * p, ///nr de valori unice
                r = n - q - p; ///valori nefolosite
            dp[k][p] = (1LL * q * dp[k + 1][p + 1] + 1LL * r * dp[k + 1][p]) % MOD;
        }
}

void reset()
{
    for(int i = 1; i <= n; i++)
        fr[i] = 0;
}

int solve_query()
{
    reset();
    int nr_dub = 0;
    long long sol = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int val = 1; val < v[i]; val++)
            if(fr[val] < 2)
                sol = (sol + dp[i][nr_dub + (fr[val] == 1)]) % MOD;
        fr[v[i]]++;
        if(fr[v[i]] == 2)
            nr_dub++;
    }
    return sol;
}

void ReadAndSolve()
{
    f >> Q;
    while(Q--)
    {
        for(int i = 1; i <= n; i++)
            f >> v[i];
        g << solve_query() << '\n';
    }
}

int main()
{
    f >> n;
    calc_prefix();
    ReadAndSolve();
    return 0;
}