ABC 401-500/ABC425E - Count Sequences 2 - 競技プログラミング用 知識集積所

---

問題

ABC425E

必要知識

B以下レベルの内容は省略

• 順列組み合わせ※
• 二項係数※
• 剰余類環

考え方

高校数学の超典型問題。

(C1+C2+……+CN)!/(C1!*C2!*……CN!)

を計算するだけでよい。
ただし、計算機でやる場合に容易にオーバーフローすることが問題。

そこで、

(C1+C2+……+CN)!/(C1!*C2!*……*CN!)
= (C1+C2+……+CN)!/(C1!*(C2+……+CN)!) 
  * (C2+C3+……+CN)!/(C2!*(C3+……+CN)!) 
  * (C3+C4+……+CN)!/(C3!*(C4+……+CN)!) 
  * ……
  * (C(N-1)+CN)!/(C(N-1)!*CN!) 

という積にわけることにする。
そうすれば、二項係数※の積として扱うことができる。

Ciは最大でも5000なので、事前に二項係数※をパスカルの三角形の5001段目まで求めてメモ化※おくことができる。
そうすれば、あとはメモから値を探して掛け算するだけでどんな問題もすぐに答えられる。

答えはＭで割った余りを要求されているので、剰余類環の考えに従って処理する。
Ｍが素数ではないが、割り算はしないので問題はない。

解答例

解答例

注意点

通常の方法で二項係数※を求めることはできない。

今回は剰余類環の法が素数とは限らないため、割り算を(M-2)乗をかけて処理することができない。
n!/(r!*(n-r)!)で求めようとすると、失敗するので注意。

別解