Cod sursă (job #785876)

#include <fstream>
using namespace std;
ifstream cin("dejavu.in");
ofstream cout("dejavu.out");
const long long N=5e3+2,mod=1e9+7;
long long n,q,v[N],freq[N];
long long dp[N][N],aib[N],aib2[N];
void reset_aib_si_freq(int n)
{
    for(int i=1; i<=n; i++)
    {
        aib[i]=0;
        aib2[i]=0;
        freq[i]=0;
    }
}
void citeste(long long* v,long long n)
{
    for(int i=1; i<=n; i++)
        cin>>v[i];
}
void update_aib(int poz,int val,long long* aib)
{
    for(int i=poz; i<=n; i+=(i&-i))
    {
        aib[i]+=val;
    }
}

void precalc(int n)
{
    for(int i=0; i<=n; i++)
        dp[n+1][i]=1;
    for(int i=n; i>=1; i--)
    {
        for(int j=0; j*2<=i; j++)
        {
            int cate_singur=(i-1)-j*2;
            int cate_nefolos=n-cate_singur-j;

            dp[i][j]=((dp[i+1][j+1]*cate_singur)%mod+(dp[i+1][j]*cate_nefolos)%mod)%mod;
        }
    }
}
int query_aib(int val,long long* aib)
{
    int suma=0;
    for(int i=val; i>0; i-=(i&-i))
        suma+=aib[i];
    return suma;
}
int query(int n)
{
    long long ans=0,p=0;
    for(int i=1; i<=n; i++)
    {
        long long singur=query_aib(v[i]-1,aib);
        long long nefolosit=(v[i]-1)-singur-query_aib(v[i]-1,aib2);
        freq[v[i]]++;

        ans=(ans+(singur*dp[i+1][p+1])%mod+(nefolosit*dp[i+1][p])%mod)%mod;
        if(freq[v[i]]==1)
            update_aib(v[i],1,aib);
        if(freq[v[i]]==2)
        {
            update_aib(v[i],-1,aib);
            update_aib(v[i],1,aib2);
            p++;
        }
    }
    return ans;
}
void rezolva()
{
    cin>>n>>q;
    precalc(n);
    for(int i=1; i<=q; i++)
    {
        citeste(v,n);
        reset_aib_si_freq(n);
        cout<<query(n)<<'\n';
    }
}
int main()
{
    rezolva();
    cin.close();
    cout.close();
    return 0;
}