Problem: D. The Maths Lecture
My solution:
I have 3 arrays:
- base: It contains base values of digits modulo k.
- dp: dp[i][j] is the number of suffixes of length i which equals j modulo k.
dp[0][0] = 1
dp[i+1][(j+base[i]*d)%k] += dp[i][j] where (1 <= i < n) & (0 <= j < k) & ((i == n-1 ? 1 : 0) <= d <= 9)
- dp2: dp2[i][j] is the number of prefixes of length i which equals j modulo k.
dp2[0][0] = 1
dp2[i+1][(j+base[n-1-i]*d)%k] += dp2[i][j] where (1 <= i < n) & (0 <= j < k) & ((i == 0 ? 1 : 0) <= d <= 9)
res equals (dp[n][0] + dp[n-1][0] * (dp2[1][1] + dp2[1][2] + ... + dp2[1][k-1]) + ... + dp[1][0] * (dp2[n-1][1] + ...)) % m
This way seemed correct to me, but it outputs 835 instead of 590 for the 3rd test case. What's my mistake?
you are counting same values twice or more.
for 5 3 1103
33333 — u count it 5 times :)
I think that I count 33333 only in dp[n][0]. I don't count it in others because prefixes are also 0 modulo 3. Can you elaborate it?
print your answer w/o modulo m
It's 114444.
75594 — correct answer.
I know that mine is wrong. I just could't point out where the error is.
why would you need a prefix i didnt need it... there is absolutely no reason to use dp2 it would just get more complicated
Can you explain your solution?
Although I miserably failed to solve this problem during the contest, at a first glance it seemed like a very classic DP question (it actually is). The problem I think you're having to understand as to why the solution provided in the editorial works is because you're thinking that you are "constructing" the numbers from left to right. When I believe they happen to be constructing it from right to left. Basically, if they have to form a 5-number digit n=5 (XXXXX) with a suffix that is divisible by K = 100. Once they reach a given a position where the current number is divisible by 100 ie : (XX100, XX200, XX300, XX400, ..., XX900), they just need to know how many numbers can fit in the "empty buckets" (XX).
I hope you understand why I'm trying to say.
well i defined dp[i][j] as the number of numbers with i digits which have j as their modulo with k which AND THEY DON'T HAVE ANY SUFFIXES WHICH HAS ZERO MODULO thats the only trick and you should watch out that we should count numbers like 9000000 because 0 is included in the thing we have before so we should add that and for every dp[i][0] we have dp[i][0] * (10 ^ (n — i — somenumbecalculateityourselfmymindisbusy) * 9) except dp[n][0] (it has alotta special cases if i didn't include them please comment about it)