Cod sursa(job #2613738)

Utilizator As932Stanciu Andreea As932 Data 10 mai 2020 16:23:01
Problema Diviz Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <string>
using namespace std;

ifstream cin("diviz.in");
ofstream cout("diviz.out");

const int MOD=30103;

int k,a,b;
int cif[205],pr[10],aft[10][205],dp[2][250][100];
string sir;

int main()
{
    cin>>k>>a>>b;
    cin>>sir;

    for(int i=0;i<sir.length();i++)
        cif[i+1]=sir[i]-'0';

    for(int i=sir.length();i>0;i--)
    {
        pr[cif[i]]=i;
        for(int c=0;c<=9;c++)
            aft[c][i]=pr[c];
    }

    for(int c=1;c<=9;c++)
        dp[1][aft[c][1]][c%k]=1;

    int l=0,ans=0;
    for(int d=1;d<=b;d++)
    {
        for(int i=1;i<=sir.length();i++)
        {
            for(int r=0;r<k;r++)
            {
                if(!dp[1-l][i][r])
                    continue;

                for(int c=0;c<=9;c++)
                    dp[l][aft[c][i+1]][(r*10+c)%k]=(dp[l][aft[c][i+1]][(r*10+c)%k]+dp[1-l][i][r])%MOD;
            }

            if(d>=a)
                ans=(ans+dp[l][i][0])%MOD;
        }

        for(int i=1;i<=sir.length();i++)
            for(int r=0;r<k;r++)
                dp[1-l][i][r]=0;

        l=1-l;
    }

    cout<<ans;

    return 0;
}