Cod sursa(job #2472014)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 11 octombrie 2019 21:48:42
Problema Diviz Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

typedef long long ll;

const int MOD = 30103;

int add(int a, int b)
{
    a += b;
    if (a >= MOD)
    {
        return a - MOD;
    }
    if (a < 0)
    {
        return a + MOD;
    }
    return a;
}

int mul(int a, int b)
{
    return a * b % MOD;
}

const int N = 200 + 7;
const int K = 100 + 7;

int dp[N][K], ndp[N][K]; /// dp[last][rest]
int n, k, a, b;
string s;
int c[N], last[10];
int ans;

int main()
{
    freopen ("diviz.in", "r", stdin);
    freopen ("diviz.out", "w", stdout);

    cin >> k >> a >> b >> s;
    n = (int) s.size();

    for (int i = 1; i <= n; i++)
    {
        c[i] = s[i - 1] - '0';
    }

    if (a == 1)
    {
        set <int> cifs;
        for (int i = 1; i <= n; i++)
        {
            if (c[i] && c[i] % k == 0)
            {
                cifs.insert(c[i]);
            }
        }
        ans += (int) cifs.size();
        a++;
    }


    for (int i = 1; i <= n; i++)
    {
        if (c[i] && last[c[i]] == 0)
        {
            dp[i][c[i] % k] = 1;
        }
        last[c[i]] = i;
    }
    for (int len = 2; len <= b; len++)
    {
        for (int c = 0; c <= 9; c++)
        {
            last[c] = 0;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int r = 0; r < k; r++)
            {
                int nr = (r * 10 + c[i]) % k;
                /// sum[r][i - 1] - sum[r][last[c[i]] - 1]
                for (int j = last[c[i]]; j < i; j++)
                {
                    ndp[i][nr] = add(ndp[i][nr], dp[j][r]);
                }
            }
            last[c[i]] = i;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int r = 0; r < k; r++)
            {
                dp[i][r] = ndp[i][r];
                ndp[i][r] = 0;
            }
            if (len >= a)
            {
                if (dp[i][0])
                {
                  ///  cout << len << ", " << i << " : " << dp[i][0] << "\n";
                }
                ans = add(ans, dp[i][0]);
            }
        }
    }

    cout << ans << "\n";



    return 0;
}