I found a topics that nCr % P can be calculated in o(P) pre processing and lg(n) query.

I have no idea how it is done. Can anybody help me regarding this topics. Any idea, or any link. Thanks in advance.

Anyone wants to play chess with me !!! :p

probelm : http://www.lightoj.com/volume_showproblem.php?problem=1318 code :http://pastebin.com/HVyHX3hx verdict: wa

I have doubt that my approach to this problem is correct. I am gonna describe my idea in brief , please somebody verify where am I wrong.

The basic task is to count number of valid pairs that satisfies constraints mentioned in the problem. If we have 'K' alphabets,how many pair of strings of length 'L' we can get where the strings of a pair has a mismatch at exactly 'M' positions.

I tried to convert the problem into coloring a 2*L grid. We have to color a 2*L grid with K colors where exactly L-M columns has to be colored with same color and the rest columns must have two different colors in their cells.

we can choose (L-M) fixed columns in C(L,L-M) ways and we can color each column with any of the K colors. Therefore we have K^(L-M) ways for L-M columns.

(Now we have rest M columns where we need to ensure mismatch. For each column we can put any of the K colors in the first row and for the next row we have K-1 choice. Therefore we have K*(K-1) ways to color a column. There are M such columns. Therefore we have (K*(K-1))^M) ways to color these columns. )*#confusion_1

Therefore we have N= C(L,L-M) * K^(L-M) * (K*(K-1))^M) pairs.

(The pairs always repeat each other).*#confusion_2 So, I toke N=N/2 , not directly , mathematically

I am not sure about #confusion_1 and #confusion_2 (enclosed by a first bracket). Someone please verify the bug of my idea.

http://community.topcoder.com/stat?c=problem_statement&pm=10804

This problem is Member SRM 474 div2 500 problem. Since it is a member SRM, there is no editorial. I cant understand the solution code even. But I am very much interested to understand the solution of this problem and then I will try to solve it.

Please help me understanding the idea of the solution of this problem. I am stuck on this problem.