Cod sursa(job #7497)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 21 ianuarie 2007 16:20:47
Problema Diviz Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NMAX 220
#define KMAX 110
#define P 30103

char N[NMAX];
int cate[NMAX][KMAX], cnt[NMAX][KMAX], c10[10][NMAX][KMAX];
int i, j, k, K, A, B, NC, c, r, t;

int main()
{
	freopen("diviz.in", "r", stdin);

	scanf("%d %d %d", &K, &A, &B);

	scanf("%s", N + 1);
	NC = strlen(N + 1);

	memset(cate, 0, sizeof(cate));
	memset(c10, 0, sizeof(c10));

	for (i = 1; i <= NC; i++)
	{
		c = N[i] - '0';

		for (j = 1; j <= B; j++)
			for (k = 0; k < K; k++)
				cnt[j][k] = 0;

		if (c > 0)
			cnt[1][c % K] = 1; // % P

		for (j = 1; j < B; j++)
			for (k = 0; k < K; k++)
				if (cate[j][k])
			{
				r = (10 * k + c) % K;
				cnt[j + 1][r] = (cnt[j + 1][r] + cate[j][k]) % P;
			}

		for (j = 1; j <= B; j++)
			for (k = 0; k < K; k++)
			{
				cnt[j][k] = (cnt[j][k] - c10[c][j][k] + P) % P;
				c10[c][j][k] = (c10[c][j][k] + cnt[j][k]) % P;
				cate[j][k] = (cate[j][k] + cnt[j][k]) % P;
			}
	}

	freopen("diviz.out", "w", stdout);

	t = 0;

	for (j = A; j <= B; j++)
		t = (t + cate[j][0]) % P;

	printf("%d\n", t);

	return 0;
}