KINV - Dãy nghịch thế độ dài K

Tác giả: skyvn97

Ngôn ngữ: C++

#include<stdio.h>
#define MAX   10101
const int MOD=1e9;
int a[MAX];
int b[13][MAX];
int p[MAX];
int n,k,r;
void init(void) {
    scanf("%d",&n);
    scanf("%d",&k);
    int i,j;
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&a[i]);
        p[i]=i+(i&(-i));
    }
    for (i=1;i<=k;i=i+1)
        for (j=1;j<=n;j=j+1)
            b[i][j]=0;
    r=0;
}
void update(int t,int x,int val) {
    while ((0<x) && (x<n+1)) {
        b[t][x]=(b[t][x]+val)%MOD;
        x=p[x];
    }
}
int sum(int t,int x) {
    int s=0;
    while ((0<x) && (x<n+1)) {
        s=(s+b[t][x])%MOD;
        x=x&(x-1);
    }
    return (s);
}
void process(void) {
    int i,j;
    for (i=n;i>=1;i=i-1) {
        update(1,a[i],1);
        r=(r+sum(k-1,a[i]-1))%MOD;
        for (j=2;j<k;j=j+1) update(j,a[i],sum(j-1,a[i]-1));
    }
    printf("%d",r);
}
int main(void) {
    init();
    process();
    return 0;
}

Download