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

Download