Cod sursa(job #2504183)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 4 decembrie 2019 16:53:17
Problema Diviz Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 205;
const int MOD = 30103;
char s[NMAX];
int dif[11][NMAX][NMAX];
int dp[NMAX][NMAX];
int c[NMAX][NMAX];

int main() {
    int k, a, b;
    freopen("diviz.in", "r", stdin);
    freopen("diviz.out", "w", stdout);
    scanf("%d%d%d\n", &k, &a, &b);
    scanf("%s", s + 1);
    int n = (int)strlen(s + 1);
    for(int i = 1; i <= n; i++) {
        int cif = s[i] - '0';
        for(int l = 1; l <= b; l++) {
            for(int r = 0; r < k; r++) {
                int rest = (r * 10 + cif) % k;
                c[l + 1][rest] += dp[l][r];
                c[l + 1][rest] %= MOD;
            }
        }
        if(cif != 0) {
            c[1][cif % k]++;
        }
        for(int l = 1; l <= b; l++) {
            for(int r = 0; r < k; r++) {
                if(dif[cif][0][0] > 0) {
                    c[l][r] -= dif[cif][l][r];
                    c[l][r] = (dp[l][r] + MOD) % MOD;
                }
                dif[cif][l][r] = (dif[cif][l][r] + c[l][r]) % MOD;
            }
        }
        dif[cif][0][0]++;
        for(int l = 1; l <= b; l++) {
            for(int r = 0; r < k; r++) {
                dp[l][r] += c[l][r];
                dp[l][r] %= MOD;
                c[l][r] = 0;
            }
        }
    }
    int sol = 0;
    for(int i = a; i <= b; i++) {
        sol += dp[i][0];
        sol %= MOD;
    }
    printf("%d\n", sol);
    return 0;
}