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;
}