Cod sursă (job #786207)

#include <stdio.h>
#include <stdlib.h>
#define MAXN 5000
#define MOD 1000000007
int aib1[MAXN+1],aib0[MAXN+1],f[MAXN+1],v[MAXN+1],c[MAXN+1][MAXN];
int n,q;
FILE *fin,*fout;
void add(int a[MAXN+1],int pos,int x) {
    do {
        a[pos]+=x;
        pos+=pos&-pos;
    } while(pos<=n);
}
int sum(int a[MAXN+1],int pos) {
    int s=0;
    while(pos) {
        s+=a[pos];
        pos&=pos-1;
    }
    return s;
}
void init(int a[MAXN+1],int n,int val) {
    int i,j;
    for(i=1; i<=n; i++) {
        a[i]=val;
    }
    for(i=1; i<=n; i++) {
        j=i+(i&-i);
        if(j<=n) {
            a[j]+=a[i];
        }
    }
}
void dp() {
    int i,k,p,unice,nefolosite;
    for(i=0; i<n; i++) {
        c[n][i]=1;
    }
    for(k=n-1; k>=0; k--) {
        for(p=0; p<=k/2; p++) {
            unice=k-2*p;
            nefolosite=n-p-unice;
            c[k][p]=(unice*1LL*c[k+1][p+1]+nefolosite*1LL*c[k+1][p])%MOD;
        }
    }
}
int ranking() {
    int i,duble,unice,pairs=0;
    long long nrord=0;
    for(i=0; i<n; i++) {
        unice=sum(aib0,v[i]-1);
        duble=sum(aib1,v[i]-1);
        nrord+=(unice*1LL*c[i+1][pairs]+duble*1LL*c[i+1][pairs+1])%MOD;
        if(f[v[i]]==0) {
            add(aib1,v[i],1);
            add(aib0,v[i],-1);
        } else {
            add(aib1,v[i],-1);
        }
        f[v[i]]++;
        if(f[v[i]]==2) {
            pairs++;
        }
    }
    return nrord%MOD;
}
void query() {
    int i,j,rez;
    fscanf(fin,"%d%d",&n,&q);
    dp();
    for(i=0; i<q; i++) {
        for(j=0; j<n; j++) {
            fscanf(fin,"%d",&v[j]);
        }
        for(j=0; j<=n; j++) {
            f[j]=0;
        }
        init(aib0,n,1);
        init(aib1,n,0);
        rez=ranking();
        fprintf(fout,"%d\n",rez);
    }
}

int main() {
    fin=fopen("dejavu.in","r");
    fout=fopen("dejavu.out","w");
    query();
    fclose(fin);
    fclose(fout);
    return 0;
}