Cod sursă (job #786620)

#include <bits/stdc++.h>

#define f first
#define s second
#define ll long long

using namespace std;

const ll M = 1e9 + 7;
const int nMax = 5000;
const int pMax = 2500;

ifstream fin("dejavu.in");
ofstream fout("dejavu.out");

ll n, q, v[nMax], dp[nMax + 5][pMax + 5], fr[nMax + 5];

void input();
void precalc();
void init();
void solveQuery();

int main()
{
    input();
    precalc();
    while(q--)
        solveQuery();

    return 0;
}

void input()
{
    fin >> n >> q;
}

void precalc()
{
    for(int j = 0; 2 * j <= n; j++)
        dp[n][j] = 1;
    for(int i = n - 1; i; i--) {
        for(int j = 0; 2 * j <= i; j++) {
            int unpaired = i - 2 * j;
            int unused = n - j - unpaired;
            dp[i][j] = (unpaired * dp[i + 1][j + 1] % M + unused * dp[i + 1][j] % M) % M;
        }
    }
}

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

int singles(int pos)
{
    int cnt = 0;
    for(int i = 1; i < v[pos]; i++) {
        if(!fr[i])
            cnt++;
    }
    return cnt;
}

int doubles(int pos)
{
    int cnt = 0;
    for(int i = 1; i < v[pos]; i++) {
        if(fr[i] == 1)
            cnt++;
    }
    return cnt;
}

void solveQuery()
{
    init();
    for(int i = 1; i <= n; i++)
        fin >> v[i];
    int sum = 0, nPairs = 0;
    for(int i = 1; i <= n; i++) {
        sum = (sum + doubles(i) * dp[i][nPairs + 1] % M + singles(i) * dp[i][nPairs] % M) % M;
        fr[v[i]]++;
        nPairs += (fr[v[i]] == 2);
    }
    fout << sum << '\n';
}