Pagini recente » Cod sursa (job #3005214) | Cod sursa (job #2236734) | Cod sursa (job #533110) | Cod sursa (job #566944) | Cod sursa (job #2716914)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("diviz.in");
ofstream fout("diviz.out");
const int mod = 30103;
const int NMAX = 202;
const int KMAX = 101;
int K, A, B, N, dp[2][NMAX][KMAX], nxt[NMAX][10], new_rest[KMAX][10], ind = 1, ans;
string s;
/// dp[lg][i][rest] - numarul de subsiruri de lungime lg, care se termina la pozitia i in sir(si o contin)
/// si au restul rest la impartirea cu K
void add_self(int &a, int b) {
a += b;
if(a >= mod)
a -= mod;
}
int main() {
fin >> K >> A >> B >> s;
N = s.size();
for(int c = 0; c < 10; ++c)
nxt[N][c] = N;
for(int i = N - 1; i >= 0; --i)
for(int c = 0; c < 10; ++c)
if(c == (s[i] - '0'))
nxt[i][c] = i;
else
nxt[i][c] = nxt[i + 1][c];
for(int i = 0; i < K; ++i)
for(int c = 0; c < 10; ++c)
new_rest[i][c] = (i * 10 + c) % K;
for(int c = 1; c < 10; ++c)
dp[1][nxt[0][c]][c % K] = 1;
for(int lg = 1; lg <= B; ++lg, ind ^= 1)
for(int i = 0; i < N; ++i)
for(int rest = 0; rest < K; ++rest) {
if(lg >= A && rest == 0)
add_self(ans, dp[ind][i][0]);
for(int c = 0; c < 10; ++c)
add_self(dp[ind ^ 1][nxt[i + 1][c]][new_rest[rest][c]], dp[ind][i][rest]);
dp[ind][i][rest] = 0;
}
fout << ans << '\n';
}