Cod sursă (job #786715)

#include <bits/stdc++.h>
#define MAX 5008
#define MOD 1000000007

using namespace std;

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

int dp[MAX][MAX/2];
/// in cate moduri completam un prefix de lungime i cu j perechi de numere
int N,Q;
int sir[MAX];
int aibApp0[MAX],aibApp1[MAX];
bool found[MAX];

void read()
{
    fin>>N>>Q;
}

void init_dp()
{
    int i;
    for(i=0;i<=N/2;++i)
        dp[N][i]=1;
}

void calc_dp()
{
    int i,j;
    for(i=N-1;i;--i)
        for(j=0;j<=i/2;++j)
        {
            int appTwice=j;
            int appOnce=i-2*j;
            int appNone=N-appOnce-appTwice;
            dp[i][j]=(1LL*appNone*dp[i+1][j]%MOD+1LL*appOnce*dp[i+1][j+1]%MOD)%MOD;
        }
}

int ub(int x)
{
    return x&(-x);
}

void add(int pos,int val,int aib[])
{
    while(pos<=N)
    {
        aib[pos]+=val;
        pos+=ub(pos);
    }
}

int sum(int pos,int aib[])
{
    int sm=0;
    while(pos)
    {
        sm+=aib[pos];
        pos-=ub(pos);
    }
    return sm;
}

void init()
{
    int i;
    for(i=1;i<=N;++i)
    {
        aibApp0[i]=ub(i);
        aibApp1[i]=0;
        found[i]=0;
    }
}

int answer_query()
{
    int i;
    int ap0=N,ap1=0,ap2=0;
    int total=0;
    for(i=1;i<=N;++i)
    {
        int val=sir[i];
        int appearedNone=sum(val-1,aibApp0);
        int appearedOnce=sum(val-1,aibApp1);
        int comb=1LL*appearedNone*dp[i][ap2]%MOD+1LL*appearedOnce*dp[i][ap2+1]%MOD;
        total=(total+comb%MOD)%MOD;
        if(!found[val])
        {
            found[val]=1;
            add(val,-1,aibApp0);
            add(val,1,aibApp1);
            --ap0;
            ++ap1;
        }
        else
        {
            add(val,-1,aibApp1);
            --ap1;
            ++ap2;
        }
    }
    return total;
}

void solve()
{
    while(Q--){
        int i;
        for(i=1;i<=N;++i)
            fin>>sir[i];
        init();
        fout<<answer_query()<<'\n';
    }
}

int main()
{
    read();
    init_dp();
    calc_dp();
    solve();
    return 0;
}