yukicoder No.523 LED

問題

No.523 LED - yukicoder

解法

LEDをポチポチする順番を順列にして考えてみると, 例えばN=3のとき, ①①②②③③の並べ方を数える問題になります. このとき, 同じ番号のものは区別せず, 場合の数は \frac{6!}{2^3} = 90となります. 一般のNに対して答えは次の式で表されることがわかります.
P_N = \frac{(2N)!}{2^N}
制約から (2N)!はループを回しながら剰余をとっても間に合います. 2^Nは, まず繰り返し二乗法を用いて k = 2^N \space mod \space pとなるkを求めた後, さらに繰り返し二乗法を用いてフェルマーの小定理
k^{-1} \space \equiv \space k^{p-2} \space mod \space p
からkの逆元を求め, k^{-1}(2N)!を計算して答えです.

提出

#278769 No.523 LED - yukicoder

その他

実は答えの式 P_N = \frac{(2N)!}{2^N} は
(2N)! = \prod_{k=1}^n (2k-1)2k
より
\frac{(2N)!}{2^N} = \prod_{k=1}^n (2k-1)k
と変形できるため, 一回のfor文で求めることもできます. ｽｺﾞｲ