INCVN - INCSEQ VN
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<cstring>
const int MOD = 5000000, VAL = 1e5 + 1, N = 10000;
int inc[N], bit[VAL+1], n, k, a[N];
void update(int idx, int v) {
for(; idx <= VAL; idx += idx & -idx)
bit[idx] = (bit[idx] + v) % MOD;
}
int sum(int idx) {
long long res = 0;
for(; idx > 0; idx -= idx & -idx)
res += bit[idx];
return res % MOD;
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 0; i < n; ++i) {
scanf("%d", a+i);
++a[i]; inc[i] = 1;
}
for(int l = 2; l <= k; ++l) {
memset(bit, 0, sizeof bit);
for(int i = 0; i < n; ++i) {
update(a[i], inc[i]);
inc[i] = sum(a[i] - 1);
}
}
long long res = 0;
for(int i = 0; i < n; ++i) res += inc[i];
printf("%d\n", int(res % MOD));
return 0;
}