Help needed in a question!

Revision en1, by siddhi, 2019-10-14 17:59:23

Can some explain how to go about this question.

https://www.codechef.com/OCT19A/problems/JIIT

I tried something like this :

Rather than applying Q operations row-column, I considered performing Q operations on rows and columns independently. What I needed to calculate was Dp[Q] vector ith index would denote the number of permutations of Q length with exactly i elements with odd frequencies.

I came up with this recurrence:

DP( n, i) = i*DP( n-1, i-1) + (N-i)*DP( n-1, i+1)

But failed in this approach because I could not do that within Time Limit with Matrix Exponentation.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English siddhi 2019-10-14 17:59:23 625 Initial revision (published)