Codeforces Round #287 Problem D - The Maths Lecture

Problem Statement:
507D - The Maths Lecture

Solution:
An insightful use of dynamic programmings in number theoretic combinatorics...

The idea is for each length i, we wan to compute how many y with length i are there such that it is exactly divisible by k. Hence for each y with length i, digit 0-9 can be padded in front of y to form x. However, we do not want any y to be a suffix of another y, as it will lead to double counting of x. How should we approach the problem?



Let D[i][j] be the number of suffixes y with length i such that when divided by k, their remainder will be j. In other words, y is in in range [i .. N-1]. To compute D[i][j], imagine we already know all D[i+1][j] for all j. We iterate through all possible digits d from 0 to 9:
1. We are intending to place digit d at position i.
2. Let val = d * \(10^{i-1}\).
3. Now, for every j = 1 to K-1, we do the following update:
    3.1  D[i][j+val (mod k)] += D[i+1][j]. This means that after padding position i with digit d, we are left with position [i+1..N-1] to fill in. But we already know how many ways we can fill in [i+1..N-1] such that the result will be j (mod k). That's how the updates come about.
    3.2 Also, for the case where j + val (mod k) is zero, that means we found the number of ways to have suffixes y with length i such that they are 0 (mod k). Store and update this information in another array ways[i].
    3.3 We also increment D[i][val (mod k)] by one. Furthermore, we also increment ways[i] if j is not equal to 0 and val (mod k) is zero, since that means we found another suffix with length i.

Finally, each ways[i] represent the number of suffixes y with length i, hence the total number of x can be computed by iterating through ways[i] and by counting the number of ways of padding digits to transform each y to x.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

long long dp[1003][103];
long long ways[1003];
int N;
long long K, MOD;
int main(){
    scanf("%d",&N);
    cin >> K;
    cin >> MOD;
    long long pow10 = 1;
    for(int i=N;i>=1;--i){
        for(int j=0;j<10;++j){
            if(i == 1 && j == 0) continue;
            long long val = (pow10 * j)%K;
            if(i == N){
                dp[i][(int)val]++;
                dp[i][(int)val]%= MOD;
                if(val==0 && j != 0) {
                    ways[i]++;
                    ways[i] %= MOD;
                }
                continue;
            }
            for(int k=1;k<K;++k){
                dp[i][(k+(int)val)%K] += dp[i+1][k];
                dp[i][(k+(int)val)%K] %= MOD;
                if(j!= 0 && (k+(int)val)%K==0) {
                    ways[i] += dp[i+1][k];
                    ways[i] %= MOD;
                }
            }
            dp[i][val%K]++;
            if(j!=0 && val%K==0)ways[i]++;
        }
        pow10 *= 10LL;
        pow10 %= K;
    }
    long long pq = 1;
    long long ans = 0;
    for(int i=1;i<=N;++i){
        ans += ways[i] * pq;
        ans %= MOD;
        if(i==1)pq *= 9LL;
        else pq *= 10LL;
        pq %= MOD;
    }
    cout << ans << endl;
    return 0;
}