Cod sursa(job #163570)

Utilizator tvladTataranu Vlad tvlad Data 22 martie 2008 14:47:21
Problema Sandokan Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 9-a Marime 1.15 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 5000;
const int NP = 700;
const int MOD = 2000003;

int n, k;
int np, pr[NP];
int c[N+1];
int cnk[NP];

void ciur() {
	bool* prime = new bool[n+1];
	memset(prime,true,n+1);
	prime[0] = prime[1] = false;
	for (int i = 2; i <= n; ++i) {
		if (prime[i]) {
			pr[np++] = i;
			for (int j = 2; i*j <= n; ++j) prime[i*j] = false;
		}
	}
	// Un fleac, m-au ciuruit
}

void add ( int x, int w ) {
	for (int i = 0; i < np; ++i) {
		for (; x % pr[i] == 0; x /= pr[i], cnk[i] += w);
	}
}

void precalc() {
	memset(cnk,0,sizeof(cnk));
	c[0] = 1;
	for (int i = 1; i <= n; ++i) {
		add(i+k-1,1);
		add(i,-1);
		c[i] = 1;
		for (int j = 0; j < np; ++j) {
			for (int e = 0; e < cnk[j]; ++e) {
				c[i] = (c[i]*pr[j]) % MOD;
			}
		}
	}
}

int main() {
	freopen("sandokan.in","rt",stdin);
	freopen("sandokan.out","wt",stdout);
	scanf("%d %d",&n,&k);
	ciur();
	precalc();
	int r = 1;
	for (int x = n; x >= k; x -= k-1) {
		int y = 0;
		for (int i = 0; i < x-k+1; ++i) y = (y+c[i]) % MOD;
		r = (r*y) % MOD;
	}
	printf("%d\n",r);
	return 0;
}