Cod sursă (job #786183)

#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], BIT[NMAX], BIT_dub[NMAX];

int n, Q;

///AIB
void update(int i)
{
    while(i < n)
    {
        BIT[i] ++;
        i += (i & -i);
    }
}
int query(int i)
{
    int sum = 0;
    while(i > 0)
    {
        sum += BIT[i];
        i -= (i & -i);
    }
    return sum;
}

void update_dub(int i)
{
    while(i < n)
    {
        BIT_dub[i] ++;
        i += (i & -i);
    }
}
int query_dub(int i)
{
    int sum = 0;
    while(i > 0)
    {
        sum += BIT_dub[i];
        i -= (i & -i);
    }
    return sum;
}
///

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

}

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;
        }
}

int solve_query()
{
    reset();
    int nr_dub = 0, nr_unic = 0, nr_rest = 0;
    long long sol = 0;
    for(int i = 1; i <= n; i++)
    {
        int x = query_dub(v[i] - 1); ///nr de duble mai mici decat v[i]
        nr_unic = query(v[i] - 1) - x;
        nr_rest = v[i] - 1 - nr_unic - x;
        ///
        sol = (sol + 1LL * nr_unic * dp[i][nr_dub + 1]) % MOD;
        sol = (sol + 1LL * nr_rest * dp[i][nr_dub]) % MOD;
        ///
        if(fr[v[i]] == 0)
            update(v[i]);
        else
            update_dub(v[i]);
        fr[v[i]]++;
        nr_dub += (fr[v[i]] == 2);
    }
    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;
}