Cod sursa(job #910928)

Utilizator ELHoriaHoria Cretescu ELHoria Data 11 martie 2013 10:39:05
Problema Diviz Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <string>
#include <algorithm>
#include <functional>

using namespace std;

ifstream cin("diviz.in");
ofstream cout("diviz.out");

const int mod = 30103, KMAX = 200, NMAX = 202;
int K, A, B;
int L;
string N;

int dp[2][NMAX][KMAX];
int T[NMAX][10];

void getMod(int &val){ val -= val < mod ? 0 : mod;}

int solve() {
	for(int c = 0;c < 10;c++) {
		T[L][c] = -1;
	}
	for(int i = L - 1;i >= 0;i--) {
		for(int c = 0;c < 10;c++) {
			T[i][c] = T[i + 1][c];
		}
		T[i][N[i] - '0'] = i;
	}
	for(int c = 0;c < 10;c++) {
		if(T[0][c] != -1) {
			dp[0][T[0][c]][c%K] = 1;
		}
	}
	int line = 0;
	int ret = 0;
	for(int l = 1;l <= B;l++,line = 1 - line) {
		for(int i = 0;i < L;i++) {
			if(A <= l) {
				ret += dp[line][i][0];
				getMod(ret);
			}
			if(l == B) continue;
			for(int r = 0, nextR;r < K;r++) {
				for(int c = 0;c < 10;c++) {
					if(T[i + 1][c] == -1) continue;
					nextR = (r*10 + c)%K;
					dp[1 - line][T[i + 1][c]][nextR] += dp[line][i][r];
					getMod(dp[1 - line][T[i + 1][c]][nextR]);
				}
				dp[line][i][r] = 0;
			}
		}
	}
	return ret;
}

int main()
{
	cin>>K>>A>>B;
	cin.get();
	getline(cin,N);
	L = (int)N.size();
	cout<<solve();
	return 0;
}