2015年1月31日 星期六

2015/01/31 Codeforces 507D. The Maths Lecture

// http://codeforces.com/contest/507/problem/D
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

int DP[2000][200] = {0};
int N, K, M;

int Ans = 0;

int pwd(int x, int n)
{
    if( n == 0 ) return 1;

    int p = pwd(x, n/2);

    if( n&1 ) return (ll)p*p%M*x%M;
    else return (ll)p*p%M;
}

int num(int x)
{
    if( x == 0 ) return 1;
    else return (ll)pwd(10, x-1)*9%M;
}

int main()
{
    scanf("%d %d %d", &N, &K, &M);

    for(int i = 1; i <= 9; i++)
        DP[0][i%K] = (DP[0][i%K]+1)%M;

    Ans += (ll)(DP[0][0])*num(N-1)%M;
    Ans %= M;

    for(int Ni = 1, ti = 10; Ni < N; Ni++)
    {
        for(int i = 0; i <= 9; i++)
            for(int Ki = 1; Ki < K; Ki++)
            {
                DP[Ni][(i*ti+Ki)%K] += DP[Ni-1][Ki];
                DP[Ni][(i*ti+Ki)%K] %= M;
            }

        for(int i = 1; i <= 9; i++)
            DP[Ni][i*ti%K] = (DP[Ni][i*ti%K]+1)%M;

        Ans += (ll)DP[Ni][0]*num(N-1-Ni)%M;
        Ans %= M;

        ti *= 10;
        ti %= K;
    }

    printf("%d\n", Ans);
}

沒有留言:

張貼留言