PROBLEM LINK:
- a
- b
0 voters
Summary
This text will be hidden
Title
Hidden contentAuthor: Yuri Shilyaev
Tester: Hasan Jaddouh
Editorialist: Yury Shilyaev
Rajkumar
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Dynamic programming, modular arithmetic.
PROBLEM:
You are given a long integer N that is represented by concatenating string M with itself K times. You are allowed to change some digits of N to other ones, but each original digit can be changed at most once. The task is to find the number of sets of changes, such that N after changing the digits can be divided by 3001 without remainder.
QUICK EXPLANATION:
Let’s first find N mod 3001 without any changes. The idea how to do that can help in full solution.
EXPLANATION:
Let’s calculate f[d][rem], the number of positions i in N, such that N_i = d and 10^i \equiv rem (mod 3001). Of course, just by iterating M we can find cnt[d][rem] - the same number just in string M, and now we have to expand it to M repeated K times.
Let’s consider some digit M_i. It repeats on positions i, i + |M|, \dots, i + |M| * (K - 1). This means, that for some d and some rem, we need to first add cnt[d][rem] to f[d][rem], then multiply rem by 10^{|M|} and get rem', again add cnt[d][rem] to f[d][rem'] and repeat this procedure K times.
We know, that when we take some rem and multiply it by constant factor (10^{|M|}), the remainders would somewhere make a cycle.
Because mod is only 3001, we can find the cycle by simply iterating to K and multiplying rem, until we reach that cycle.
Now, we should add cnt[d][rem] to add f values on precycle, and add cnt[d][rem] \cdot \lfloor \frac{K - |precycle|}{|cycle|} \rfloor to all f values of the cycle. The last iteration by cycle could stop at any remainder, so we need to add cnt[d][rem] also on prefix of the cycle with size (K - |precycle|) mod |cycle|.
This values are already enough to calculate N mod 3001. Now we need to think what to do with the changes.
Let’s transform our dynamic programming f[d][rem] to can[d][rem], where can[d][rem] is the number of ways we can achieve remainder rem, if we consider all the digits d in N, while one digit among could be changed to any other one.
New dynamic programming is easily achieved from the old one. We firstly just summarize f[d][rem] \cdot d \cdot rem, of all rem (this is the remainder we get without any changes). And then also iterating digit to, that we made a change d → to at some position. If we iterate rem that to gave to original remainder, we add to can[d][sum - rem \cdot (d - to)] all the ways to choose such pair (to, rem) (it is simply f[to][rem]).
Hell yes, we found for each digit all the possible remainders it can bring to the changed N. Now let’s code modular knapsack and achieve the answer. You can look on the setter’s solution, it does everything described above clearly.
The total complexity is O(3001^2 * 10).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.