Cod sursa(job #2716914)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 5 martie 2021 21:53:14
Problema Diviz Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#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';
}