siddhi's blog

By siddhi, history, 10 months ago, In English,

Can some explain how to go about this question.

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it