PROBLEM LINK:Author: Praveen Dhinwa with help of Alexey Zayakin PREREQUISITESdp, fft, karstuba, binomial theorem, multinomial theorem, combinatorics, matrix exponentiation PROBLEMFind number of numbers of $N$ digits divisible by $P$ having their sum of digits $\leq M$. As number could grow very large, print answer modulo $998244353$. CREDITSI want to thank Praveen Dhinwa for helping me in writing some parts of the editorial. I have also incorporated ideas from Alexey and Shang too. QUICK EXPLANATIONWe will visualize the process of creating n digit number from left to right (i.e. from LSB (Lowest significant bit) to MSB (Most significant bit)). This visualization will help us in constructing a typical dynamic programming solution. We can first write a simple dp having states (current place, sum of digits, remainder). It is too slow and only pass subtask 1. But we can optimize it by using the fact that $P$ is too small. We can observe that putting $x$ at the $i^{th}$ place (from LSB to MSB) contributes $(x * 10^i) \, \% \, P$ into the remainder and it adds $x$ to the sum of digits. Let us say $10^i \, \% \, P$ to be contributing remainder by $i^{th}$ digit to the number formed. We will group the places by their contributing remainders. So we will do a dp in which we will iterate over their contributes remainders (which goes from $0$ to $P  1$ rather than $N$). Let us make an array $cnt[i]$ which denotes number of places having contributing remainder equal to $i$. Mathematically it is number of $x (0 \leq x < N)$ such that $10^x \% P = i$. For finding this $cnt$ array, you can simply use digit dp. You can also use the fact of periodicity of $10^x \% P$. At this point, you can also make an interesting and useful observation that distinct values of $cnt[i]$ won't be too much. There indeed will be at most $4$ distinct values of $cnt[i]$ and these are $(0, 1, x  1, x)$ for some $x$. It can be easily proved if we consider how to calculate $cnt[i]$ using the fact that $(10^i \mod P)$ is periodic. Let us define function $f: f[i][d]$ as number of ways of having sum of digits = $d$ for all the positions having contributing remainder equal to i. If we know how to compute $f$ faster, then we can use an $\mathbb{O}(M^2 P^2)$ dp to solve the third subtask. State of that dp will be (at which contributing remainder we currently are, cur_sum_of_digits, cur_rem): For computing $f$ faster, we can use matrix exponentiation, binomial theorem, multinomial theorem and combinatorics ideas, Few very basic details are given in this section. Please see next section fore more details. Let's fix contributing remainder as $r$, Let $f[i][d]$ denote the number of ways having first $i$ places of number we want to construct such that it is having sum of digits equal to $d$. Note that we are considering in all the positions having contributing remainder equal to $r$.
Let us write a bivariate polynomial as follows. $$ \large \prod_{i = 0}^{P  1} \sum_{j = 1}^{m} coef[i][j] x^j y^{(i j) \% P)}$$ We have to find coefficient of $x^m y^0$ in it. Note that we can convert this bivariate polynomial into univariate by using a smart trick described in next section. As we noticed the DP transition is a multiplication by some matrix. We can notice that this matrix has exactly $P$ independent components (each of size $M + 1$), thus we can consider these components independently. Inside each component multiplication by matrix is equal to multiplication by some polynomial which can be done by FFT or Karatsuba's multiplication algorithm. EXPLANATIONSimplest DP idea for solving subtask 1 Let's start by solving the problem using a simple DP. We need to count strings of length $N$, with sum of digit $X$, which are divisible by $P$. Since it's a counting problem, we can try solving it by DP. The DP depends on the number of digits added so far, their remainder modulo $P$ and their sum of digits. Let $dp[n][rem][sum]$ = how many strings of length $n$ have remainder rem modulo $P$ and their sum of digit is $sum$. The answer is obviously $dp[N][0][X]$. The standard initialization in counting problems is to consider a "fictitious" string  of length $0$ (like we added nothing). In this case, adding nothing translates to $dp[0][0][0] = 1$. Let's see the recurrence. How can we reduce the problem from length $N$ to length $N  1$? By fixing the first digit (for example). Suppose the first digit is $c$. It adds $10^n*c$ to the remainder and also it adds $c$ to the sum of digits. So let's iterate $c$ from $0$ to $9$. Now first digit is fixed. How to count the rest? We need to add to $dp[n][rem][sum]$ the value $dp[n  1][rem'][sum  c]$, where $rem' + 10^n * c = rem$. This approach times out for big values of $n$, but it's fast enough to pass the first subtask. Let's change the DP We somehow have to get rid of that $n$ factor. Let's take a closer look to what DP actually does  the value of $n$ is important because it determines value of $10^n * c$, for the first digit added. But now it comes the interesting part  that is $10^n$ $modulo P$. This means, there are only $P$ possible distinct answers for all $10^n$ values. This means, we can group the values $n$ by the value $10^n modulo P$. What do we get by doing this? The idea is to add digits for a group at the same time. Let's Denote $cnt[x]$ = number of values $y (0 \leq y < N)$ such as $10^y mod P = x$. Let's assume for now this array calculated. Suppose we know that $cnt[0] = 4$ and $cnt [1] = 3$ . There will be $4$ positions (let's note them $p_1, p_2, p_3, p_4$) such as $10^{p_1} = 10^{p_2} = 10^{p_3} = 10^{p_4} = 0 (modulo P)$. If we assign them digits d1, d2, d3, d4, the remainder modifies by $10^{p_1} * d1 + 10^{p_2} * d2 + 10^{p_3} * d3 + 10^{p_4} * d4 = 10^{p_1} * (d1 + d2 + d3 + d4) = 0 * (d1 + d2 + d3 + d4) = 0.$ Let's consider the other example: $cnt [1] = 3.$ There will be 3 positions (p1, p2, p3) such as $10^{p_1} = 10^{p_2} = 10^{p_3} = 1 (modulo P)$. If we assign them digits d1, d2, d3, the remainder modifies by $10^{p_1} * (d1 + d2 + d3) = 1 * (d1 + d2 + d3)$. The idea is to iterate over $i$ from $0$ to $P  1$. Let's consider $cnt[i]$ positions for the given $i$. We can fix what digits we add. They will have a sum of digits (let's note it $sd$). Then, the remainder modifies by $i * sd$ and sum of digits modifies by $sd$. We have a new DP. Let $dp[g][rem][sum]$ = in how many ways can we obtain remainder rem modulo $P$ and sum of digits $sum$ if we considered only first $g$ groups of positions $(cnt[0], cnt[1], ..., cnt[g  1])$. For the current group we can iterate the sum of digits we assign to it. This uniquely modifies the remainder and the sum of digits. So, for a calculated $dp[g][rem][sum]$, let's iterate $sd$, representing sum of digits added for positions corresponding to group $g + 1$. We get the recurrence $dp[g + 1][(rem + g * sd) \, \% \, P][sum + sd]$ += $dp[g][rem][sum] * ways[g][sd]$. You probably wonder what ways can be. We assigned a sum of digits. It needs to be divided between $cnt[g + 1]$ positions. This means, we need to assign to cnt[g + 1] positions values between 0 and 9 such as, after adding all those values from the positions, we get the sum sd. This is ways[g][sd] = in how many ways can we distribute sum of digits sd to $cnt[g]$ positions, such as in each positions we're allowed to add numbers between 0 and 9. If we can calculate tables cnt and ways efficiently, we're done. We'll calculate firstly cnt, then ways. Calculating values of cnt
Using one of those approaches, we can compute array cnt. Calculate the array ways As a quick recap: ways[g][sd] = in how many ways can we split sum of digits sd to cnt[g] positions. Denote by now n = cnt[g]. We have to count how many equations satisfy: $x[1] + x2 + .... + x[n] = sd$ such that $0 \le x[i] \le 9$ This is a classical problem. There are lot of ways of solving such problem.
Solving the hardest subtask
Actually theoritically the first method should be faster, but practically, the second method worked slightly faster than first method. You can see [Praveen's solution][] for solution based on the first method. Please see [Alexey's Solution][] for second method. Reasons for not hiding modulo Please share any other idea you have regarding the problem !! AUTHOR'S AND TESTER'S SOLUTIONS:asked 16 Feb '15, 15:23

"Multiplying two polynomials in a prime field can be done using Number Theoretic Transform" Can you please explain this. There are very less resources on net for NTT. Also why this multiplication cannot be achieved by FFT. I realized that FFT fails to give correct answers for large modulo like 10^9+7 and 998244353. Why is NTT left as the only option. I don't know the reason ? answered 16 Feb '15, 15:46

modulo value is wrong , btw answered 16 Feb '15, 15:32

Please add more explanation for the calculation of f using inclusion exclusion principle. answered 17 Feb '15, 03:50

http://www.codechef.com/viewsolution/6247282 why my solution is wrong answer even though it satisfies all the testcode answered 20 Feb '15, 14:33

Neither IE nor Chrome works well on this page,what should i do? answered 02 Mar '15, 09:18

Answer is hidden as author is suspended. Click here to view.
answered 02 Jun '16, 02:44
