Cod sursă (job #811991)

#include <bits/stdc++.h>
using namespace std;

typedef int ll;
const int MOD = 1000000007;

int N, Q;
vector<vector<int>> fdp;

void precomputeDP(int N) {
    fdp.assign(N+1, vector<int>(N+1, 0));
    for (int s = N; s <= 2 * N; s++){
        for (int A = max(0, s - N); A <= s/2; A++){
            int T = s - A;
            if(T > N) continue;
            if(s == N){
                fdp[A][T] = 1;
            } else {
                long long ways = 0;
                if(A > 0) {
                    ways = (1LL * A * fdp[A-1][T]) % MOD;
                }
                if(T - A > 0) {
                    ways = (ways + 1LL * (T - A) * fdp[A][T-1]) % MOD;
                }
                fdp[A][T] = ways % MOD;
            }
        }
    }
}

struct Fenw {
    int n;
    vector<int> fenw;
    Fenw(int n): n(n), fenw(n+1,0) { }
    void update(int i, int delta) {
        for(; i <= n; i += i & -i)
            fenw[i] += delta;
    }
    int query(int i) {
        int s = 0;
        for(; i; i -= i & -i)
            s += fenw[i];
        return s;
    }
};

void solveQuery() {
    vector<int> seq(N);
    for (int i = 0; i < N; i++){
        cin >> seq[i];
    }
    vector<int> freq(N+1, 0);
    int A = N, T = N;
    Fenw bit0(N), bit1(N);
    for (int d = 1; d <= N; d++){
        bit0.update(d, 1);
    }
    long long rank = 0;
    for (int i = 0; i < N; i++){
        int x = seq[i];
        int cnt0 = bit0.query(x - 1);
        int cnt1 = bit1.query(x - 1);
        if (cnt0 > 0 && A > 0) {
            rank = (rank + 1LL * cnt0 * fdp[A-1][T]) % MOD;
        }
        if (cnt1 > 0 && (T - A) > 0) {
            rank = (rank + 1LL * cnt1 * fdp[A][T-1]) % MOD;
        }
        if (freq[x] == 0) {
            freq[x] = 1;
            A--;
            bit0.update(x, -1);
            bit1.update(x, +1);
        }
        else if (freq[x] == 1) {
            freq[x] = 2;
            bit1.update(x, -1);
            T--;
        }
    }
    cout << rank % MOD << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("dejavu.in", "r", stdin);
    freopen("dejavu.out", "w", stdout);
    cin >> N >> Q;
    precomputeDP(N);
    while(Q--) {
        solveQuery();
    }
    return 0;
}