Cod sursa(job #1074033)

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

const int MAX_N = 202;
const int MAX_K = 102;
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)
                for(int c = 0; c < 10; ++c)
                    D[l ^ 1][M[j + 1][c]][k1[k][c]] += D[l][j][k], D[l ^ 1][M[j + 1][c]][k1[k][c]] %= MOD;
        }
    }

    g << sol << "\n";

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

    return 0;
}