Cod sursa(job #741968)

Utilizator ProtomanAndrei Purice Protoman Data 27 aprilie 2012 17:27:41
Problema Diviz Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <algorithm>
#include <stdio.h>

#define restRez 30103
#define MAX 210

using namespace std;

int k, a, b, n, sol;
char strBuff[MAX];
int pos[MAX][MAX][10], ds[MAX][MAX];

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

	scanf("%d %d %d\n", &k, &a, &b);

	fgets(strBuff + 1, MAX, stdin);

	for (; strBuff[n + 1] != '\n'; n++);

	for (int i = 1; i <= n; i++)
	{
		int c = strBuff[i] - '0';

		for (int l = b; l > 1; l--)
			for (int r = 0; r < k; r++)
				ds[l][r] = pos[l][r][c];

		for (int l = b; l > 1; l--)
			for (int r = 0; r < k; r++)
				for (int uc = 0; uc < 10; uc++)
					pos[l][(10 * r + c) % k][c] = (pos[l][(10 * r + c) % k][c] + pos[l - 1][r][uc]) % restRez;

		for (int l = b; l > 1; l--)
			for (int r = 0; r < k; r++)
				pos[l][r][c] = (pos[l][r][c] + restRez - ds[l][r]) % restRez;

		if (c)
			pos[1][c % k][c] = 1;
	}

	for (int c = 0; c < 10; c++)
		for (int i = a; i <= b; i++)
			sol = (sol + pos[i][0][c]) % restRez;

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

	fclose(stdin);
	fclose(stdout);
	return 0;
}