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

Download