Cod sursa(job #917684)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 11:30:41
Problema Diviz Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <string>
#include <cstring>
using namespace std;
ifstream cin("diviz.in");
ofstream cout("diviz.out");
const int mod = 30103, KMAX = 100, NMAX = 202;
int K, A, B;
int L;
string N;
int dp[2][NMAX][KMAX];
int T[NMAX][10];
inline void getMod(int &val){ val -= val < mod ? 0 : mod;}
int solve() {
memset(T,-1,sizeof(T));
for(int c = 0;c < 10;c++) {
int t = -1;
for(int i = L;i > 0;i--) {
t = ((N[i - 1] - '0') == c ? i : t); 
T[i - 1][c] = t;
}
}
for(int c = 1;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 = l;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++) {
if(!dp[line][i][r]) continue;
for(int c = 0;c < 10;c++) {
if(T[i][c] == -1) continue;
nextR = (r*10 + c);
while(nextR >= K) nextR -= K;
dp[1 - line][T[i][c]][nextR] += dp[line][i][r];
getMod(dp[1 - line][T[i][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;