Cod sursa(job #1446454)

Utilizator akaprosAna Kapros akapros Data 1 iunie 2015 21:04:37
Problema Diviz Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 202
#define Kmax 102
#define mod 30103
using namespace std;
int n, i, j, k, a, b, r, cif;
int d[2][Nmax][Kmax];
int D[2][Nmax][Kmax];
int sol, v[Nmax];
int first[11][Nmax];
char s[Nmax];
int main()
{
    freopen("diviz.in", "r", stdin);
    freopen("diviz.out", "w", stdout);
    scanf("%d %d %d\n", &k, &a, &b);
    gets(s + 1);
    n = strlen(s + 1);
    for (i = 1; i <= n; ++ i)
      {
          v[i] = s[i] - '0';
          ++ d[1][i][v[i] % k];
          D[1][i][v[i] % k] = D[1][i - 1][v[i] % k] + d[1][i][v[i] % k];
      }
    for (i = n; i >= 1; -- i)
    for (j = 0; j <= 9; ++ j)
    if (v[i] != j)
    first[j][i] = first[j][i + 1];
    else first[j][i] = i;
    if (1 >= a) sol = D[1][n][0];
    for (i = 1; i < n; ++ i)
    {
        for (j = 1; j <= n; ++ j)
         for (r = 0; r < k; ++ r)
           for (cif = 0; cif <= 9; ++ cif)
             if (first[cif][j + 1])
           {
               d[(i + 1) % 2][first[cif][j + 1]][(r * 10 + cif) % k] =
               ( D[i % 2][j][r] + d[(i + 1) % 2][first[cif][j + 1]][(r * 10 + cif) % k]) % mod;
               /*D[(i + 1) % 2][first[cif][j + 1]][(r * 10 + cif) % k] =
                (D[(i + 1) % 2][first[cif][j + 1]][(r * 10 + cif) % k] +
                  d[(i + 1) % 2][first[cif][j + 1]][(r * 10 + cif) % k] ) % mod; */
           }

        for (j = 1; j <= n; ++ j)
         for (r = 0; r < k; ++ r)
          D[(i + 1) % 2][j][r] =(D[(i + 1) % 2][j - 1][r] + d[(i + 1) % 2][j][r]) % mod;
        if (i + 1>= a && i + 1<= b)
        sol = (sol + D[(i + 1) % 2][n][0]) % mod;
        memset(d[i % 2], 0, sizeof(d[i % 2]));
        memset(D[i % 2], 0, sizeof(D[i % 2]));
    }
    printf("%d", sol);
    return 0;
}