Pagini recente » Cod sursa (job #885673) | Cod sursa (job #247643) | Cod sursa (job #1216845) | Arhiva de probleme | Cod sursa (job #1410069)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("diviz.in");
ofstream fout("diviz.out");
const int MOD = 30103;
char sir[205], snul[11];
int K, A, B, N, sol;
int Next[205][11], Rest[105][11];
int dp[2][205][101]; //dp[j][i][r] - numarul de moduri de a alege subsiruri distincte de lungime j care contin ca ultima cifra cea de-a i-a cifra a numarului N, subsiruri care sa dea restul r la impartirea K
int main()
{
fin >> K >> A >> B;
fin.getline(snul, 11);
fin.getline(sir + 1, 205);
N = strlen(sir + 1);
for (int i = N; i >= 1; --i)
for (int c = 0; c <= 9; ++c)
{
Next[i][c] = Next[i + 1][c];
if (sir[i] - '0' == c)
Next[i][c] = i;
}
for (int rest = 0; rest <= K - 1; ++rest)
for (int c = 0; c <= 9; ++c)
Rest[rest][c] = (rest * 10 + c) % K;
for (int c = 1; c <= 9; ++c)
if (Next[1][c])
dp[0][Next[1][c]][c % K] = 1;
int l = 1;
for (int j = 1; j <= B; ++j, l = 1 - l)
{
for (int i = 1; i <= N; ++i)
for (int rest = 0; rest <= K - 1; ++rest)
dp[l][i][rest] = 0;
for (int i = 1; i <= N; ++i)
{
if (j >= A)
{
sol += dp[1 - l][i][0];
sol %= MOD;
}
for (int rest = 0; rest <= K - 1; ++rest)
{
if (!dp[1 - l][i][rest])
continue;
for (int c = 0; c <= 9; ++c)
{
if (Next[i + 1][c])
{
dp[l][Next[i + 1][c]][Rest[rest][c]] += dp[1 - l][i][rest];
dp[l][Next[i + 1][c]][Rest[rest][c]] %= MOD;
}
}
}
}
}
fout << sol << '\n';
fin.close();
fout.close();
return 0;
}