Cod sursa(job #3266182)

Utilizator nistor_dora_valentinaNistor Dora Valentina nistor_dora_valentina Data 6 ianuarie 2025 12:47:17
Problema Diviz Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <cstring>

using namespace std;
ifstream fin("diviz.in");
ofstream fout("diviz.out");
int k, a, b, i, j, n, dp[205][205][105], first[11][205], fr[27], ans, mod=30103;
char s[205];
int main()
{
    fin>>k>>a>>b>>s;
    n=strlen(s);
    for(i=0; i<n; i++)
        for(int cif=0; cif<=9; cif++)
          first[cif][i]=-1;
    for(i=0; i<n; i++)
    {
        if(fr[s[i]-'0']==0 && s[i]-'0'!=0)
            dp[1][i+1][(s[i]-'0')%k]++;
        fr[s[i]-'0']++;
    }
    for(int cif=0; cif<=9; cif++)
        first[cif][n]=-1;
    for(i=n-1; i>=0; i--)
    {
        for(int cif=0; cif<=9; cif++)
            if(cif==s[i]-'0')
              first[cif][i]=i;
            else
              first[cif][i]=first[cif][i+1];
    }
    for(int l=2; l<=b; l++)
    {
        for(i=l-1; i<n; i++)
          for(int r=0; r<k; r++)
            for(int cif=0; cif<=9; cif++)
              if(first[cif][i]!=-1)
                 dp[l][first[cif][i]][(r*10+cif)%k]=(dp[l][first[cif][i]][(r*10+cif)%k]+dp[l-1][i][r])%mod;
    }
    for(int l=a; l<=b; l++)
        for(i=0; i<n; i++)
            ans=(ans+dp[l][i][0])%mod;
    fout<<ans;
    return 0;
}