Cod sursa(job #272619)

Utilizator CezarMocanCezar Mocan CezarMocan Data 7 martie 2009 15:30:48
Problema Diviz Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <cstring>
#define maxn 210
#define mod 30103

using namespace std;

int k, a, b, n, i, j, q, c, x;
int v[2][maxn][maxn];
int t[maxn], p[10][maxn], sol;
char s[maxn];
int md[2000];

int main() {
	freopen("diviz.in", "r", stdin);
	freopen("diviz.out", "w", stdout);
	
	scanf("%d%d%d ", &k, &a, &b);
	fgets(s, 210, stdin);
	
	md[0] = 0;
	for (i = 1; i <= 2000; i++) {
		md[i] = md[i - 1] + 1;
		if (md[i] == k)
			md[i] -= k;
	}
	
	for (i = 0; s[i]; i++) 
		t[i + 1] = s[i] - 48;
	n = i;

	for (c = 0; c < 10; c++)
		for (i = 1; i <= n; i++)
			for (j = i; j <= n; j++)
				if (t[j] == c) {
					p[c][i] = j;
					break;
				}
		
	for (i = 1; i < 10; i++)
		v[0][p[i][1]][i % k]++; 
	
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) 
			for (q = 0; q < k; q++) {
				if (i >= a && i <= b && q == 0) {
					sol += v[0][j][q];
					if (sol > mod)
						sol -= mod;
				}
				
				for (c = 0; c < 10; c++) 
					if (p[c][j + 1]) {
						x = md[q * 10 + c];
						v[1][p[c][j + 1]][x] += v[0][j][q];
						if (v[1][p[c][j + 1]][x] >= mod)
							v[1][p[c][j + 1]][x] -= mod;
					}
					
			}
		memcpy(v[0], v[1], sizeof(v[1]));
		memset(v[1], 0, sizeof(v[1]));
	}
	
	printf("%d\n", sol);
	
	return 0;
}