Problem Link : -

https://www.codechef.com/COOK110A/problems/ANGGRA

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"