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; }