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

Download