Cod sursa(job #20559)

Utilizator love_for_uSpancioc Riana love_for_u Data 21 februarie 2007 19:05:22
Problema Diviz Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define aduna(a, b) ( ((a += b) >= MOD) ? (a -= MOD) : 0 )
#define INF 900000000
#define MOD 30103
#define NMAX 205
#define CMAX 11

int N, K, A, B;
char s[NMAX];

int nou[NMAX][NMAX], vechi[NMAX][NMAX], fst[CMAX][NMAX], S[CMAX][NMAX], cnt = 0;
int rst[4505];

int main(void)
{
    int l, i, r, c, cif, uz[CMAX], x;

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

    scanf("%d %d %d", &K, &A, &B);

    for (i = 1; i < 4500; i++) rst[i] = i % K;

    scanf("%s", s + 1);

    N = strlen(s + 1);

    for (cif = 0; cif < 10; cif++)
    {
        fst[cif][N+1] = INF;
        for (i = N; i >= 1; i--)
            if (s[i] - '0' != cif)
                  fst[cif][i] = fst[cif][i+1];
            else  fst[cif][i] = i;
    }


    memset(uz, 0, sizeof(uz));
    for (i = 1; i <= N; i++)
        c = s[i]-'0',
        vechi[i][rst[c]] = (!uz[c] && c),
        uz[c] = 1;

    if (A == 1)
       for (i = 1; i <= N; i++)
           aduna(cnt, vechi[i][0]);

    for (l = 2; l <= B; l++)
    {
        memset(nou, 0, sizeof(nou));
        for (i = l-1; i < N; i++)
            for (r = 0; r < K; r++)
                for (cif = 0; cif < 10; cif++)
                {
                       x = fst[cif][i+1];
                       if (x == INF) continue;
                       /* daca mai exista o alta cifra egala cu cif
                          intre pozitiile i+1 si x-1 */

                       aduna(nou[x][rst[r * 10 + cif]], vechi[i][r]);
                }

        if (l >= A)
           for (i = 1; i <= N; i++)
               aduna(cnt, nou[i][0]);

        memcpy(vechi, nou, sizeof(nou));
    }

    printf("%d\n", cnt);

    return 0;    
}