Cod sursa(job #2897147)

Utilizator AlexMariMarinescu Alexandru AlexMari Data 2 mai 2022 16:58:21
Problema Diviz Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("diviz.in");
ofstream fout("diviz.out");

#define MOD 30103

int n, k, nr0, a, b, ans, dp[205][205][105];

char s[205];

int main()
{
    fin >> k >> a >> b;
    fin >> (s + 1);
    n = strlen(s + 1);
    dp[1][1][(s[1] - '0') % k] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i][1][(s[i] - '0') % k] = 1;
        for (int j = 1; j < i; j++) {
            for (int rest = 0; rest < k; rest++) {
                dp[i][j][rest] += dp[i - 1][j][rest];
                dp[i][j][rest] %= MOD;
                int curr_rest = (rest * 10 + s[i] - '0') % k;
                dp[i][j + 1][curr_rest] += dp[i - 1][j][rest];
                dp[i][j + 1][curr_rest] %= MOD;
            }
        }
        if (dp[i][1][s[i] - '0'] == 1 && s[i] == '0') {
            dp[i][1][0] = 0;
            nr0++;
        }
    }

    for (int i = a; i <= b; i++) {
        ans += dp[n][i][0];
        ans %= MOD;
    }

    if (a == 1) {
        ans += nr0;
        ans %= MOD;
    }
    fout << ans;
    return 0;
}