## Tuesday, January 27, 2015

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