Cod sursa(job #3217224)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 21 martie 2024 20:23:00
Problema Diviz Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("diviz.in");
ofstream fout("diviz.out");
int n,k,a,b,l,sol,j,i,cif,D[2][205][205],ant[205][13];
const int MOD=30103;
string s;
int t;
int main()
{
    fin>>k>>a>>b;
    fin>>s;
    s="0"+s;
    n=s.size();
    for(i=n-1;i>=0;i--)
    {
        for(cif=0;cif<=9;cif++)
            ant[i][cif]=ant[i+1][cif];
        if(i<n-1)
            ant[i][s[i+1]-'0']=i+1;
    }
    t=1;
    for(i=1;i<=9;i++)
        D[t][ant[0][i]][i%k]++;
    sol=0;
    for(l=2;l<=b;l++)
    {
        memset(D[1-t],0,sizeof(D[1-t]));
        for(i=l-1;i<n;i++)
            for(j=0;j<k;j++)
                if(D[t][i][j])
                    for(cif=0;cif<=9;cif++)
                        if(ant[i][cif])
                            D[1-t][ant[i][cif]][(j*10+cif)%k]=(D[1-t][ant[i][cif]][(j*10+cif)%k]+D[t][i][j])%MOD;
        if(l>=a)
            for(i=l;i<n;i++)
                sol=(sol+D[1-t][i][0])%MOD;
        t=1-t;
    }
    fout<<sol;
    return 0;
}