Cod sursa(job #13684)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 7 februarie 2007 13:09:54
Problema Diviz Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <cstring>

const int NMAX = 204;
const int NCIF = 10;
const int KMAX = 102;
const int TMAX = 1024;
const int MOD = 30103;

int N, K, A, B;
int V[NMAX], T[TMAX];
int first[NMAX][NCIF];
int DP[2][NMAX][KMAX];
int cnt;

void read() {
	FILE *fin = fopen("diviz.in", "rt");
	char buf[NMAX];

	fscanf(fin, " %d %d %d ", &K, &A, &B);

	fgets(buf, 256, fin);

	for (N = 0; '0' <= buf[N] && buf[N] <= '9'; ++N)
		V[N] = buf[N] - '0';

	fclose(fin);
}

void prething() {
	int i, Q[NCIF];

	memset(Q, 0xff, sizeof(Q));

	for (i = 0; i <= N; ++i) {
		memcpy(first[i], Q, sizeof(Q));
		Q[V[i]] = i;
	}

	for (i = 0; i < TMAX; ++i)
		T[i] = i < K ? i : T[i - K];
}

void dinamica() {
	int i, j, k, t, t1, c, *p;

	for (i = 0; i < N; ++i)
		if (V[i] != 0) {
			DP[1][i][T[V[i]]] = 1;

			if (A == 1 && first[N][V[i]] == i && T[V[i]] == 0) ++cnt;
		}

	for (i = 2; i <= B; ++i) {
		t = i & 1; t1 = t ^ 1;
		
		memset(DP[t], 0x00, sizeof(DP[t]));

		for (j = 0; j < N; ++j) {
			for (c = 0; c < NCIF; ++c)
				if (first[j][c] != -1)
					for (k = 0; k < K; ++k) {
						p = &DP[t][j][ T[k * 10 + V[j]] ];
						*p += DP[t1][ first[j][c] ][k];
						if (*p >= MOD) *p -= MOD;
					}

			if (i >= A && first[N][V[j]] == j) {
				cnt += DP[t][j][0];
				if (cnt >= MOD) cnt -= MOD;
			}
		}
	}

}

void write() {
	FILE *fout = fopen("diviz.out", "wt");

	fprintf(fout, "%d\n", cnt);

	fclose(fout);
}

int main() {
	
	read();

	prething();

	dinamica();

	write();

	return 0;
}