Cod sursa(job #2618852)

Utilizator eusebiu_alexandruMorar Eusebiu eusebiu_alexandru Data 26 mai 2020 13:54:37
Problema Diviz Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 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[1-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;
	
}