Cod sursa(job #2451648)

Utilizator CharacterMeCharacter Me CharacterMe Data 27 august 2019 15:42:48
Problema Diviz Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>
#define MOD 30103
///N=10^200-1
///K=100
///A=200
///B=200
using namespace std;
///
int a, b, k, i, j, l, p, q, out;
int sol[201][201][100], nxt[201][10], last[10];
char lst[201];
///
void read();
void solve();
void write();
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("diviz.in", "r", stdin);
    scanf("%d%d%d", &k, &a, &b);
    fgetc(stdin);
    fgets(lst, 201, stdin);
    l=strlen(lst)-1;
    fclose(stdin);
}
void solve(){
    for(i=0; i<10; ++i) last[i]=l+1;
    for(i=l; i>=0; --i) {
        for(j=0; j<10; ++j) nxt[i][j]=last[j];
        last[lst[i-1]-'0']=i;
    }
    for(i=1; i<10; ++i) sol[1][nxt[0][i]][i%k]=1;
    for(i=1; i<b; ++i){
        for(q=0; q<k; ++q){
            for(j=i; j<=l; ++j){
                if(!sol[i][j][q]) continue;
                for(p=0; p<=9; ++p) sol[i+1][nxt[j][p]][(q*10+p)%k]=(sol[i+1][nxt[j][p]][(q*10+p)%k]+sol[i][j][q])%MOD;
            }
        }
    }
    for(i=a; i<=b; ++i){
        for(j=1; j<=l; ++j) out=(out+sol[i][j][0])%MOD;
    }
}
void write(){
    freopen("diviz.out", "w", stdout);
    printf("%d", out);
    fclose(stdout);
}