INCVN - INCSEQ VN
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <vector>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 5000000;
int n, k;
int a[10010], pos[10010], F[10010], bit[10010];
pair<int,int> b[10010];
void add(int i, int v) {
for(;i<=n;i+=i&(-i)) bit[i] = (bit[i] + v) % MOD;
}
int get(int i) {
int r = 0;
for(;i>0;i&=(i-1)) r = (r + bit[i]) % MOD;
return r;
}
int main() {
scanf("%d%d", &n, &k);
for(int i=1;i<=n;++i) {
scanf("%d", a+i);
b[i] = make_pair(a[i], -i);
}
sort( b + 1, b + n + 1);
for(int i=1;i<=n;++i) pos[-b[i].second] = i;
for(int i=1;i<=n;++i) F[i] = 1;
for(int i=2;i<=k;++i) {
memset( bit, 0, sizeof(bit));
for(int j=1;j<=n;++j) {
int tmp = get(pos[j]);
add(pos[j], F[j]);
F[j] = tmp;
}
}
int result = 0;
for(int i=1;i<=n;++i) result = (result + F[i]) % MOD;
printf("%d\n", result);
return 0;
}