Problem Link : -
Hey, Guys!!
Grandfather is angry , so lets please solve this problem :-)
Part-1 discusses the brute-force solution which does not pass the test cases but clears up many thing about the problem.
For the real solution, refer Part-2 .
Part-1 : -
Say, M=4 and N=5
dp[i][j] means the number of sequences of length 'i' which have "j" prefix-sums divisible by “M” .
dp[1][0]=(number of sequences of length-“1” which has prefix not divisible by “M”–>[1],[2],[3])= 3
dp[1][1]=(number of sequences of length-“1” which has one prefix divisible by “M”–>[0])= 1
dp[2][0]=(number of sequences of length-“2” which has prefix not divisible by “M”–>[1,(0,1,2)],[2,(0,1,3)],[3,(0,2,3)])= 9
dp[2][1]=(number of sequences of length-“2” which has exactly one prefix divisible by “M”–>[0,(1,2,3)],[1,3],[2,2],[3,1])= 6
dp[2][2]=(number of sequences of length-“2” which has exactly two prefixes divisible by “M”–>[0,0])= 1
Final answer will be dp[n][k] + dp[n][k+1] + dp[n][k+2] + ...... + dp[n][n],
where,
dp[n][k]=number of sequences of length "n" with "k" good prefixes
For our case, the dp-relation is given by : -
dp[i][j]= 3*dp[i-1][j] + dp[i-1][j-1]
Explanation:-
dp[i-1][j-1] means that these are guys which need just one correct value and they will become sequences of length “i” with “j” good-prefixes, each of them can be given only 1 good value, so if we have dp[i-1][j-1]=5, then 5-guys can become good
Now, dp[i-1][j] is already good, we need to add wasteful values so number of prefixes remain “j” and length becomes “i”
For each good guy, example:- 1, there are 3-values([0,1,2]…not 3, because 1+3=4, which will increase the length of array by 1 without affecting the number of good prefixes ), which don’t make any change to number of good-prefixes
Photo of the dp-table of this particular case :-
This is our lovely dp-but we can’t use it as it will give time-out
Part-2 :-
Consider this sequence of length “4” and M=4
:–> 0132
Prefix array :-0,1,4,6
0 and 4 are divisible by “M”, so the answer is : - 2(as 2 numbers are divisible by “M”)
Now, consider prefix array Modulo M :- 0,1,0,2
[Solution:- Number of zeroes in prefix-modulo array will give us the answer]
Lets repeat!!:-:
Once a great man said,
Number of zeroes in prefix-modulo array will give us the answer
Now, dp[n][k]= number of ways to put k-zeroes in the prefix-modulo array.
If we can find this, we are done…
Say k = 1, m=5, n=4
What are the number of ways to put “1” zero in an array of length “4” ?
Here are the ways :-
x,x,x,0
0,x,x,x
x,0,x,x
x,x,0,x
(4-ways)
“Mathematics say that the number of ways to arrange k-zeroes in array of length-“n” is {(N)}C_{(K)}”
There are basically, {(N)}C_{(K)}=4 ways to do this …(equation…a)
Now, for this one , say :-
x,x,x,0… what are the number of ways to give appropriate values to each “x” ?
x can be anything from [1,M-1] …so you agree that we have to fill (N-K) values with appropriate numbers ?
Number of ways to do this :- (M-1)^{N-K}
So the total number of ways(dp[n][k]) = 4 . (M-1)^{N-K} ={(N)}C_{(K)}. (M-1)^{N-K}…(as 4={(N)}C_{(K)} … fromequation -(a) )
So, now we know how to calculate the answer for dp[n][k]
Final answer, as mentioned in part-1 is :—>
dp[n][k] + dp[n][k+1] + dp[n][k+2] + ...... + dp[n][n]
Happy Coding
“Once a wise man said, coding is easy if you understand everything clearly. Clarity is true power”