Cod sursă (job #786900)

#include <bits/stdc++.h>
#define lsb(x) (x&(-x))

using namespace std;

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

const int nmax = 5e3, mod = 1e9 + 7;

struct AIB {
	int aib[nmax + 3], n = nmax;

	void add(int pos, int val) {
		for(; pos <= n; pos += lsb(pos))
			aib[pos] += val;
	}

	int prefSum(int pos) {
		int s = 0;
		for(; pos > 0; pos -= lsb(pos))
			s += aib[pos];
		return s;
	}

	void reset(int val) {
		for(int i = 1; i <= n; i++)
			aib[i] = 0;
		for(int i = 1; i <= n; i++)
			add(i, val);
	}
};

int v[nmax + 3], f[nmax + 3], dp[nmax + 3][nmax + 3];
AIB aib0, aib1;
int n, q;

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

	for(int i = n - 1; i >= 0; i--) {
		for(int j = 0; j * 2 <= i; j++) {
			int f2, f1, f0;
			f2 = j;
			f1 = i - 2 * j;
			f0 = n - f1 - f2;
			dp[i][j] = (int64_t)(f0 * dp[i + 1][j] + f1 * dp[i + 1][j + 1]) % mod;
		}
	}
}

int answer() {
	int pairs = 0, rez = 0, f0, f1;

	for(int i = 1; i <= n; i++) {
		f0 = aib0.prefSum(v[i] - 1);
		f1 = aib1.prefSum(v[i] - 1);
		rez = (int64_t)(rez + f0 * dp[i][pairs] + f1 * dp[i][pairs + 1]) % mod;

		if(f[v[i]] == 0) {
			aib0.add(v[i], -1);
			aib1.add(v[i], 1);
		} else aib1.add(v[i], -1);
		f[v[i]]++;

		if(f[v[i]] == 2)
			pairs++;
	}
	return rez;
}

void readSolve() {
	fin >> n >> q;
	aib0.n = aib1.n = n;
	preCalc();

	for(int i = 1; i <= q; i++) {
		for(int j = 1; j <= n; j++)
			fin >> v[j];

		aib0.reset(0);
		aib1.reset(1);

		fout << answer() << "\n";
	}
}

int main() {
	readSolve();
	return 0;
}