Cod sursa(job #2304320)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 17 decembrie 2018 21:38:15
Problema Diviz Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>
#define N 205
#define MOD 30103
using namespace std;

ifstream fin("diviz.in") ;
ofstream fout("diviz.out") ;

int dp[5][N][N] ;
int first[15][N] ;
int t[N],ppp[15] ;
string sir ;

int main()
{
    int k , a , b , n , j , i , lg , cf ,p ,q,qq,sol=0;
    fin >> k >> a >> b ;
    fin >> sir ;
    n = sir.size()-1;
    for ( i = 0 ; i <= n ; i++ )
        t[i+1] = sir[i]-'0' ;
    for ( i = n ; i >= 1 ; i-- )
    {
        ppp[t[i]] = i ;
        for ( j = 0 ; j <= 9 ; j++ )
            first[j][i]= ppp[j] ;
    }
    for ( i = 1 ; i <= 9 ; i++ )
        dp[1][first[1][i]][i%k] = 1 ;
    qq = 0 ;
    q = 1 ;
    for ( lg = 1 ; lg <= b ; lg++ )
    {
        q = 1-q ;
        qq = 1-qq ;
        for ( i = 1 ; i <= n ; i++ )
        {
            for ( p = 0 ; p < k ; p++ )
            {
                if ( dp[q][i][p] == 0 )
                    continue ;
                for ( cf = 0 ; cf <= 9 ; cf++ )
                    dp[qq][first[cf][i+1]][(p*10+cf)%k] = ( dp[qq][first[cf][i+1]][(p*10+cf)%k] + dp[q][i][p] ) % MOD ;
            }
            if ( lg >= a )
                sol = ( sol + dp[q][i][0] ) % MOD ;
        }
        for ( i = 1 ; i <= n ; i++ )
            for ( j = 0 ; j < k ; j++ )
                dp[q][i][j] = 0 ;
    }
    fout << sol ;
}