Cod sursa(job #2165875)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 13 martie 2018 14:09:33
Problema Diviz Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<bits/stdc++.h>
#define mod 30103
using namespace std;
int k,a,b,n,first[15][205],dp[205][2][105],line,sol;
char s[205];
int main()
{
    freopen("diviz.in","r",stdin);
    freopen("diviz.out","w",stdout);

    scanf("%d%d%d",&k,&a,&b);

    scanf("\n");
    scanf("%s",s+1);
    n=strlen(s+1);

    for(int cif=0;cif<=9;cif++)
        for(int i=0;i<=n;i++)
            for(int j=i+1;j<=n && !first[cif][i];j++)
                if(s[j]==cif+'0')
                    {
                        first[cif][i]=j;
                        break;
                    }


    for(int i=1;i<=9;i++)
        dp[first[i][0]][1][i%k]=1;

    line=1;
    for(int j=1;j<=b;j++,line^=1)
    {
        for(int i=1;i<=n;i++)
            for(int r=0;r<k;r++)
                dp[i][!line][r]=0;
        for(int i=1;i<=n;i++)
        {
            for(int r=0;r<k;r++)
            {
                if(!r && j>=a && j<=b)
                {
                    sol=(sol+dp[i][line][r]);
                    if(sol>=mod) sol-=mod;
                }
                for(int cif=0;cif<=9;cif++)
                {
                    int c=(r*10+cif)%k;
                    dp[first[cif][i]][!line][c]+=dp[i][line][r];
                   // dp[first[cif][i]][!line][(r*10+cif)%k]%=mod;
                    if(dp[first[cif][i]][!line][c]>=mod) dp[first[cif][i]][!line][c]-=mod;
                }
            }
        }
    }
    printf("%d\n",sol);
    return 0;
}