Cod sursa(job #2443339)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 27 iulie 2019 14:31:43
Problema Diviz Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>
#define MOD 30103

using namespace std;

ifstream fin("diviz.in");
ofstream fout("diviz.out");

int k, a, b, dp[101][101][101];
string x;

int solve(int index, int d, int c)
{
    if (dp[index][d][c]) return dp[index][d][c];
    if (index == x.size())
    {
        return d == 0 && c >= a && c <= b;
    }
    int nr = x[index] - '0';
    return dp[index][d][c] = solve(index + 1, (d * 10 + nr) % k, c + 1) + solve(index + 1, d, c) % MOD;
}

int main()
{
    fin >> k >> a >> b >> x;
    for (int i = a; i <= b; ++i)
    {
        dp[x.size()][0][i] = 1;
    }
    for (int i = x.size() - 1; i >= 0; --i)
    {
        for (int j = k - 1; j >= 0; --j)
        {
            for (int u = x.size() - 1; u >= 0; --u)
            {
                int nr = x[i] - '0';
                dp[i][j][u] = (dp[i + 1][(j * 10 + nr) % k][u + 1] + dp[i + 1][j][u]) % MOD;
            }
        }
    }
    fout << dp[0][0][0] << "\n";
    return 0;
}