Cod sursa(job #983764)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 12 august 2013 17:27:25
Problema Diviz Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
 
#define NMAX 201
#define KMAX 101
#define MOD 30103
 
int d[2][NMAX][KMAX],first[11][NMAX],r[2001];
char c[NMAX+1];
 
int main ()
{
    int n,i,j,k,sol,a,b,rest,last,ok,x;
    ifstream f("diviz.in");
    ofstream g("diviz.out");
    f>>k>>a>>b;
    f>>(c+1);
    f.close();
    n=strlen(c+1);
    first[c[n]-48][n]=n;
    for(i=n-1;i>=1;i--) {
        for(j=0;j<=9;j++)
            first[j][i]=first[j][i+1];
        first[c[i]-48][i]=i;
    }
    for(i=0;i<=2000;i++)
        r[i]=i%k;
    for(i=1;i<=9;i++)
        if(first[i][1])
            d[0][first[i][1]][r[i]]=1;
    sol=0;
    for(i=1,ok=1;i<=b;i++,ok=1-ok) {
        if(i>=a) {
            for(j=1;j<=n;j++) {
                sol=sol+d[1-ok][j][0];
                if(sol>=MOD)
                    sol=sol-MOD;
            }
        }
        if(i==b)
            break;
        for(j=1;j<=n;j++)
            for(rest=0;rest<=k-1;rest++)
                d[ok][j][rest]=0;
        for(j=1;j<=n;j++)
            for(rest=0;rest<=k-1;rest++) {
                if(d[1-ok][j][rest]==0)
                    continue;
                for(last=0;last<=9;last++)
                    if(first[last][j+1]) {
                        x=r[rest*10+last];
                        d[ok][first[last][j+1]][x]+=d[1-ok][j][rest];
                        if(d[ok][first[last][j+1]][x]>=MOD)
                            d[ok][first[last][j+1]][x]-=MOD;
                    }
            }
    }
    g<<sol%MOD;
    return 0;
}