Cod sursa(job #2351370)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 22 februarie 2019 12:05:20
Problema Diviz Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>

#define Nmax 205
#define Kmax 105
#define md 30103

using namespace std;

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

int N;
int dp[2][Kmax][Nmax];
int K, A, B;
char C[Nmax];
bool used[Kmax][Nmax];

int main()
{
    fin >> K >> A >> B;
    fin >> (C + 1);
    N = strlen(C + 1);
    dp[0][0][0] = 1;
    int ans = 0;
    for(int i = 1; i <= N; i++)
    {
        int dig = C[i] - '0';
        memset(dp[i & 1], 0, sizeof(dp[i & 1]));
        memset(used, false, sizeof(used));
        dp[i & 1][0][0] = 1;
        for(int rem = 0; rem < K; rem++)
        {
            int newRem = (rem * 10 + dig) % K;
            for(int k = 1 + (dig == 0); k <= min(i, B); k++)
            {
                dp[i & 1][newRem][k] = (dp[i & 1][newRem][k] + dp[1 - (i & 1)][rem][k - 1]) % md;
                if(!used[newRem][k])
                {
                    dp[i & 1][newRem][k] = (dp[i & 1][newRem][k] + dp[1 - (i & 1)][newRem][k]) % md;
                    used[newRem][k] = true;
                }
            }
        }
    }
    for(int i = A; i <= B; i++)
        ans = (ans + dp[N & 1][0][i]) % md;
    fout << ans << "\n";
    return 0;
}