Cod sursă (job #786490)

#include <bits/stdc++.h>
using namespace std;
ifstream fin ("dejavu.in");
ofstream fout ("dejavu.out");

typedef long long ll;

const int MAXN=5e3+10;
const int MOD=1e9+7;

int dp[MAXN][MAXN],aib[2][MAXN];
int n,q;

void update (bool nr, int pos, int val){
    for (int i=pos;i<=n;i+=(i&(-i)))
        aib[nr][i]+=val;
}
int query (bool nr, int pos){
    int rez=0;
    for (int i=pos;i>=1;i-=(i&(-i)))
        rez+=aib[nr][i];
    return rez;
}

void init (){
    for (int i=0;i<MAXN;++i){
        for (int j=0;j<MAXN;++j){
            dp[i][j]=-1;
        }
    }
}

void prec (){
    for (int i=n;i>=0;--i){
        for (int j=i/2;j>=0;--j){
            if (i==n) dp[i][j]=1;
            else
                dp[i][j]=(1LL*dp[i+1][j+1]*(i-2*j)%MOD+1LL*dp[i+1][j]*(n-i+j)%MOD)%MOD;
        }
    }
}

void solve (){

    for (int i=1;i<=q;++i){
        for (int j=1;j<=n;++j){
            update (0,j,-(query (0,j)-query (0,j-1))+1);
            update (1,j,-(query (1,j)-query (1,j-1)));
            //aib[1][j]=0;
        }
        int rez=0,nr2=0;
        for (int j=1;j<=n;++j){
            int x;
            fin >>x;
            int nr0=query (0,x-1),nr1=query (1,x-1);

            rez=(1LL*rez+(1LL*dp[j][nr2]*nr0%MOD+1LL*dp[j][nr2+1]*nr1%MOD)%MOD)%MOD;

            if (query (0,x)-query (0,x-1)==1){
                update (0,x,-1);
                update (1,x,1);
            }
            else{
                if (query (1,x)-query (1,x-1)==1){
                    update (1,x,-1);
                    nr2++;
                }
            }

        }
        fout <<rez<<'\n';
    }
}

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

    init ();
    prec ();

    /*for (int i=0;i<=n;++i){
        for (int j=0;j<=i/2;++j){
            fout <<dp[i][j]<<' ';
        }
        fout <<'\n';
    }*/
    solve ();
    return 0;
}