Cod sursa(job #1410069)

Utilizator Ionut228Ionut Calofir Ionut228 Data 30 martie 2015 20:39:00
Problema Diviz Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int MOD = 30103;

char sir[205], snul[11];
int K, A, B, N, sol;
int Next[205][11], Rest[105][11];
int dp[2][205][101]; //dp[j][i][r] - numarul de moduri de a alege subsiruri distincte de lungime j care contin ca ultima cifra cea de-a i-a cifra a numarului N, subsiruri care sa dea restul r la impartirea K

int main()
{
    fin >> K >> A >> B;
    fin.getline(snul, 11);
    fin.getline(sir + 1, 205);
    N = strlen(sir + 1);

    for (int i = N; i >= 1; --i)
        for (int c = 0; c <= 9; ++c)
        {
            Next[i][c] = Next[i + 1][c];
            if (sir[i] - '0' == c)
                Next[i][c] = i;
        }
    for (int rest = 0; rest <= K - 1; ++rest)
        for (int c = 0; c <= 9; ++c)
            Rest[rest][c] = (rest * 10 + c) % K;

    for (int c = 1; c <= 9; ++c)
        if (Next[1][c])
            dp[0][Next[1][c]][c % K] = 1;

    int l = 1;
    for (int j = 1; j <= B; ++j, l = 1 - l)
    {
        for (int i = 1; i <= N; ++i)
            for (int rest = 0; rest <= K - 1; ++rest)
                dp[l][i][rest] = 0;
        for (int i = 1; i <= N; ++i)
        {
            if (j >= A)
            {
                sol += dp[1 - l][i][0];
                sol %= MOD;
            }

            for (int rest = 0; rest <= K - 1; ++rest)
            {
                if (!dp[1 - l][i][rest])
                    continue;
                for (int c = 0; c <= 9; ++c)
                {
                    if (Next[i + 1][c])
                    {
                        dp[l][Next[i + 1][c]][Rest[rest][c]] += dp[1 - l][i][rest];
                        dp[l][Next[i + 1][c]][Rest[rest][c]] %= MOD;
                    }
                }
            }
        }
    }

    fout << sol << '\n';

    fin.close();
    fout.close();
    return 0;
}