Cod sursa(job #1397827)

Utilizator felixiPuscasu Felix felixi Data 23 martie 2015 19:35:40
Problema Diviz Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <string.h>
#define MOD 30103

using namespace std;

ifstream f("diviz.in");
ofstream g("diviz.out");

int k, a, b, prep[201][10], d[2][201][101], len, ind, nrsub[201], answ;
char n[205];

int main()
{
    f>>k>>a>>b;
    f>>n+1;
    len = strlen(n+1);

    for (int i=len-1; i>=0; i--)
    {
        memcpy(prep[i], prep[i+1], sizeof (prep[i]));
        prep[i][n[i+1]-'0']=i+1;
    }

    for(int i=1; i<=9; i++)
    {
        if(prep[0][i]!=0)
            d[0][ prep[0][i] ][ i%k ]++;
        nrsub[1] += d[0][ prep[0][i] ][ 0 ];
    }

    ind=1;
    for (int i = 2; i <= b; i++)
    {
        for (int j = i-1; j <= len; j++)
            for (int p = 0; p <= k-1; p++)
                if (d[1-ind][j][p])
                {
                    for (int l = 0; l <= 9; l++)
                        if (prep[j][l])
                        {
                            d[ind][prep[j][l]][(p*10+l) % k] = (d[ind][prep[j][l]][(p*10+l) % k] + d[1-ind][j][p]) % MOD;
                            if ((p*10+l) % k == 0)
                                nrsub[i]=(nrsub[i]+d[1-ind][j][p])%MOD;
                        }
                }
        ind = 1-ind;
        memset(d[ind], 0, sizeof (d[ind]));
    }

    for (int i=a; i<=b; i++)
        answ = (answ + nrsub[i])%MOD;

    g<<answ;
    return 0;
}