Cod sursa(job #74671)

Utilizator sealTudose Vlad seal Data 26 iulie 2007 21:38:35
Problema Diviz Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<stdio.h>
#include<string.h>
#define Nm 201
#define Km 100
#define Mod 30103
char S[Nm];
int k,a,b,ans;

void read()
{
    freopen("diviz.in","r",stdin);
    scanf("%d%d%d%s",&k,&a,&b,S);
}

void solve()
{
    int M[2][Nm][Km],T[Nm][Km],Last[Nm][10],A[Nm],n,l,i,r,nr,c,p;

    n=strlen(S);
    for(i=0;i<n;++i)
        A[i+1]=S[i]-'0';

    memset(Last[0],0,10*sizeof(int));
    for(i=1;i<=n;++i)
    {
        memcpy(Last[i],Last[i-1],10*sizeof(int));
        Last[i][A[i]]=i;
        memset(M[0][i],0,sizeof(M[0][i]));
        if(A[i])
            M[0][i][A[i]%k]=1;
    }

    memset(T[0],0,sizeof(T[0]));
    c=0; p=1;
    for(l=1;l<=b;++l)
    {
        for(i=1;i<=n;++i)
            memset(M[p][i],0,sizeof(M[p][i]));
        for(i=1;i<=n;++i)
            for(r=0;r<k;++r)
            {
                T[i][r]=T[i-1][r]+M[c][i][r];
                if(T[i][r]>=Mod)
                    T[i][r]-=Mod;
                if(Last[i-1][A[i]])
                {
                    T[i][r]-=M[c][Last[i-1][A[i]]][r];
                    if(T[i][r]<0)
                        T[i][r]+=Mod;
                }
                if(i<n)
                {
                    nr=(r*10+A[i+1])%k;
                    M[p][i+1][nr]+=T[i][r];
                    if(M[p][i+1][nr]>=Mod)
                        M[p][i+1][nr]-=Mod;
                }
            }
        if(l>=a)
            ans+=T[n][0];
        c^=1; p^=1;
    }
}

void write()
{
    freopen("diviz.out","w",stdout);
    printf("%d\n",ans%Mod);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}