Cod sursă (job #789215)

#include <bits/stdc++.h>

using namespace std;

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

const int mod=1e9+7;

void add(int &x,int y)
{
    x=(x+y)%mod;
}

int n,q;

int a[5005];

int dp[5005][5005];

int fr[5005];

struct AIB
{
    int aib[5005];

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

    void update(int p,int v)
    {
        for(int i=p; i<=n; i+=(i&(-i)))
            aib[i]+=v;
    }

    int query(int p)
    {
        int ans=0;
        for(int i=p; i>=1; i-=(i&(-i)))
            ans+=aib[i];
        return ans;
    }
} aib1,aib2;

int main()
{
    fin>>n>>q;

    for(int j=0; j<=n; j++)
        if((n-j)%2==0)
            dp[n][j]=1;
    for(int i=n-1; i>=1; i--)
    {
        for(int j=0; j<=i; j++)
        {
            if((i-j)%2==0)
            {
                if(j>0)
                    add(dp[i][j],1LL*j*dp[i+1][j-1]%mod);
                add(dp[i][j],1LL*(n-j-(i-j)/2)*dp[i+1][j+1]%mod);
            }
        }
    }

    while(q--)
    {
        for(int i=1; i<=n; i++)
            fin>>a[i];

        for(int i=1; i<=n; i++)
            fr[i]=0;

        aib1.init();
        aib2.init();

        int ans=0;

        int c2=0;
        for(int i=1; i<=n; i++)
        {
            int c1=aib1.query(n);
            int c1s=aib1.query(a[i]-1);
            int c2s=aib2.query(a[i]-1);

            add(ans,1LL*c1s*dp[i][c1-1]%mod);
            add(ans,1LL*(a[i]-1-c1s-c2s)*dp[i][c1+1]%mod);

            fr[a[i]]++;

            if(fr[a[i]]==1)
                aib1.update(a[i],1);
            if(fr[a[i]]==2)
            {
                aib1.update(a[i],-1);
                aib2.update(a[i],1);
            }
        }

        fout<<ans<<"\n";
    }

    return 0;
}