Cod sursa(job #1148666)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 20 martie 2014 23:14:03
Problema Diviz Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <fstream>
#include <vector>
#define MOD 30103
#include <cstring>
using namespace std;
ifstream f("diviz.in");
ofstream g("diviz.out");
int DP[205][105],Partial[205][105];
char Str[205];
int N[205];
int K,A,B;
vector <int> Rest[205];
long long Result;
void Precalc()
{
    int i,j;
    for(i=0;i<K;i++)
        for(j=0;j<K;j++)
            if((j*10)%K==i)
                Rest[i].push_back(j);
}
void initialize()
{
    int i,j;
    for(i=1;i<=N[0];i++)
        for(j=0;j<=K;j++)
            DP[i][j]=0;
}
void Browse()
{
    int i,j;
    for(i=1;i<=N[0];i++)
        if(N[i]!=0)
            DP[i][N[i]%K]++;
    if(A==1)
        Result+=DP[i][0];
    Result%=MOD;
    for(i=1;i<=N[0];i++)
        for(j=0;j<K;j++)
            Partial[i][j]=Partial[i-1][j]+DP[i][j];
    int digits=2;
    for(;digits<=B;digits++)
    {
        initialize();
        for(i=digits;i<=N[0];i++)
        {
             for(j=0;j<K;j++)
             {
                for(unsigned int k=0;k<Rest[((j-N[i])%K+K)%K].size();k++)
                    DP[i][j]+=Partial[i-1][Rest[((j-N[i])%K+K)%K][k]];
                DP[i][j]%=MOD;
             }
             if(digits>=A)
             {
                 Result+=DP[i][0];
                 Result%=MOD;
             }

        }
        for(i=1;i<=N[0];i++)
            for(j=0;j<K;j++)
            {
                Partial[i][j]=Partial[i-1][j]+DP[i][j];
                Partial[i][j]%=MOD;
            }
    }
    g<<Result<<"\n";
}
int main()
{
    f>>K>>A>>B;
    char ch;
    f.get(ch);
    f.getline(Str,205);
    for(int i=0;i<strlen(Str);i++)
        N[++N[0]]=Str[i]-'0';
    Precalc();
    Browse();
    return 0;
}