KINV - Dãy nghịch thế độ dài K
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10000 + 5, MOD = 1000000000;
int a[N], v[N], n, k, inv[N], bit[N];
void enter() {
scanf("%d%d",&n,&k);
for(int i = 0; i < n; ++i)
scanf("%d", a+i), v[i] = a[i];
}
int compress() {
sort(v, v+n); int nVal = unique(v, v+n) - v;
for(int i = 0; i < n; ++i)
a[i] = lower_bound(v, v+nVal, a[i]) - v + 1;
return nVal;
}
void add(int i, int v, int n) {
for(; i <= n; i += i & -i) bit[i] = (bit[i] + v) % MOD;
}
int sum(int i) {
int res = 0;
for(; i > 0; i -= i & -i) res = (res + bit[i]) % MOD;
return res;
}
void solve() {
int nBIT = compress();
for(int i = 0; i < n; ++i) inv[i] = 1;
for(int l = 2; l <= k; ++l) {
memset(bit, 0, sizeof bit);
for(int i = n-1; i >= 0; --i) {
add(a[i], inv[i], nBIT);
inv[i] = sum(a[i] - 1);
}
}
int res = 0;
for(int i = 0; i < n; ++i) res = (res + inv[i]) % MOD;
printf("%d\n", res);
}
int main() {
enter();
solve();
return 0;
}