Cod sursa(job #1074036)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 7 ianuarie 2014 02:14:59
Problema Diviz Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstring>
#include <fstream>
using namespace std;

const int MAX_N = 202;
const int MAX_K = 101;
const int MOD = 30103;

int N, K, A, B, sol;
int D[2][MAX_N][MAX_K], M[MAX_N][10], k1[MAX_K][10];
char s[MAX_N];

int main() {
    ifstream f("diviz.in");
    ofstream g("diviz.out");

    f >> K >> A >> B;
    f >> s;

    int N = strlen(s);
    for(int i = N; i >= 1; --i)
        s[i] = s[i - 1];

    for(int i = N; i >= 1; --i)
        for(int j = 0; j < 10; ++j)
            if(s[i] - '0' == j)
                M[i][j] = i;
            else M[i][j] = M[i + 1][j];

    for(int i = 0; i < K; ++i)
        for(int j = 0; j < 10; ++j)
            k1[i][j] = (i * 10 + j) % K;
    for(int j = 1; j < 10; ++j)
        if(M[1][j] != 0)
            ++D[1][M[1][j]][j % K];
    for(int i = 1, l = 1; i <= B; ++i, l ^= 1) {
        memset(D[l ^ 1], 0, sizeof(D[l ^ 1]));
        for(int j = 1; j <= N; ++j) {
            if(i >= A)
                sol += D[l][j][0], sol %= MOD;
            for(int k = 0; k < K; ++k)
                if(D[l][j][k])
                    for(int c = 0; c < 10; ++c)
                        if(M[j + 1][c]) {
                            D[l ^ 1][M[j + 1][c]][k1[k][c]] += D[l][j][k];
                            if(D[l ^ 1][M[j + 1][c]][k1[k][c]] >= MOD)
                                D[l ^ 1][M[j + 1][c]][k1[k][c]] -= MOD;
                        }
        }
    }

    g << sol << "\n";

    f.close();
    g.close();

    return 0;
}