TPINCD - Dãy con tăng
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 = 15111992;
int n, k, nb;
int a[10010], b[10010], pos[10010];
int F[10010];
int bit[10010], old[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);
a[++n] = 1100000000;
for(int i=1;i<=n;++i) b[nb++] = a[i];
sort( b, b + nb);
nb = unique(b, b + nb) - b;
for(int i=1;i<=n;++i) pos[i] = lower_bound( b, b + nb, a[i]) - b + 1;
for(int i=1;i<=n;++i) F[i] = 1;
++k;
for(int i=2;i<=k;++i) {
memset( bit, 0, sizeof(bit));
memset( old, 0, sizeof(old));
for(int j=1;j<=n;++j) {
int tmp = get(pos[j] - 1);
add(pos[j], -old[pos[j]]);
add(pos[j], F[j]);
old[pos[j]] = F[j];
F[j] = tmp;
}
}
printf("%d\n", F[n]);
return 0;
}