Help needed in a question!

Правка en1, от siddhi, 2019-10-14 17:59:23

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.

#### История

Правки

Rev. Язык Кто Когда Δ Комментарий
en1 siddhi 2019-10-14 17:59:23 625 Initial revision (published)