Cod sursa(job #2618873)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 26 mai 2020 14:43:40
Problema Diviz Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 200, mod = 30103;
int k, a, b, v[nmax + 5], dp[2][nmax + 5][101], first[10][nmax + 5], n;
string sir;

int main()
{
    fin >> k >> a >> b;
    fin >> sir;
    for (int i = 0; i < sir.length(); ++i)
    {
        v[i + 1] = sir[i] - '0';
        ++n;
    }
    for (int i = 0; i <= 9; ++i) first[i][n + 1] = n + 1;
    for (int i = n; i >= 1; --i)
    {
        for (int j = 0; j <= 9; ++j)
        {
            if (v[i] == j) first[j][i] = i;
            else first[j][i] = first[j][i + 1];
        }
    }
    int d = b % 2;
    for (int l = b; l >= 0; --l)
    {
        for (int i = n; i >= 0; --i)
        {
            for (int j = k - 1; j >= 0; --j)
            {
                int ans = 0;
                if (l >= a && l <= b && j == 0) ans = 1;
                int start = 0;
                if (l == 0)
                {
                    ++start;
                }
                for (int cif = start; cif <= 9; ++cif)
                {
                    int next = first[cif][i + 1];
                    if (next <= n)
                    {
                        ans = (ans + dp[1 - d][next][(j * 10 + cif) % k]) % mod;
                    }
                }
                dp[d][i][j] = ans;
            }
        }
        d = 1 - d;
    }
    fout << dp[0][0][0];
    fin.close();
    fout.close();
    return 0;
}