前計算 \(O(\sqrt{M} + \max (\sum_i C_i) \log M)\) 、テストケースあたり \(O(N \log M+\log^2 M)\) の解法があります。

step.1 問題の整理

公式解説のように、

\[\frac{(C_1+C_2+\cdots+C_N)!}{C_1! C_2! \cdots C_N!}\]

を計算します。問題になっているのは、 \(C_i!\) と \(M\) が互いに素でないときに、 \(C_i!\) の \(M\) を法とした逆元が存在しないことにより、 mod \(M\) での割り算ができないことです。

\(M=998244353\) などでは簡単に解ける問題が、mod が任意であることで難しくなっています。

step.2 中国剰余定理の適用

\(M\) を素因数分解し \(M = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}\) （\(p_i\) は素数、\(\alpha_i \ge 1\) は整数）とします。

\(M_i = p_i^{\alpha_i}\) \((1 \le i \le k)\) とします。答えを各 \(M_i\) で割った余りがすべて分かれば、 Garner のアルゴリズムを用いて \(M\) で割った余りを復元することができます。

よって、 \(M=p^\alpha\) の問題が解ければ、この問題を解くことができます。

step.3 \(M = p^{\alpha}\)

\(p\) を素数、 \(\alpha \ge 1\) を整数として \(M=p^\alpha\) とします。

\[G = \frac{(C_1+C_2+\cdots+C_N)!}{C_1! C_2! \cdots C_N!}\]

を計算します。 \(K\) を正整数として、 \(K!\) を \(p\) の累乗とその他に分けることを考えます。すなわち、非負整数 \(r(K)\) と正整数 \(f(K)\) を用いて

\[K! = p^{r(K)} \times f(K)\]

とします。ここで、 \(f(K)\) は \(p\) で割り切れないとします。そうすると、 \(f(K)\) と \(M=p^{\alpha}\) との最大公約数が \(1\) であるので、 \(f(K)\) の逆元が mod \(M\) で存在します。これを利用します。

\(G=\frac{(C_1+C_2+\cdots+C_N)!}{C_1! C_2! \cdots C_N!}\) とおくと、

\[G = p^{r(C_1+C_2+\cdots+C_N)-r(C_1)-r(C_2)-\cdots-r(C_N)}\\ \times f(C_1+C_2+\cdots+C_N)\\ \times f(C_1)^{-1} \times f(C_2)^{-1} \times \cdots \times f(C_N)^{-1}\]

と表されます。よって、\(r(k)\) と \(f(k), f(k)^{-1} \bmod M\) をそれぞれ前計算することにより、 \(G\) を \(O(N)\) 時間で計算することができます。

ここで、 \(G\) は正整数であるので、\(r(C_1+C_2+\cdots+C_N)-r(C_1)-r(C_2)-\cdots-r(C_N) \ge 0\) であることは保証されます。

step.4 計算量評価

\(M\) の素因数の種類数 \(k\) が \(O(\log M)\) 個で抑えられます。これを利用します。

まず、 \(M\) を素因数分解するのでそれを行うだけの時間計算量がかかります。

各 \(M_i = p_i^{\alpha_i}\) における計算量は、

• 前計算：mod 998244353 での階乗前計算のように行うと、合計 \(O(\max (\sum_i C_i))\) 時間
• クエリあたり： \(G\) の計算に合計 \(O(N)\)

となり、\(\log M\) を掛けて前計算 \(O(\max (\sum_i C_i) \log M)\) 時間、 クエリあたり \(O(N \log M)\) 時間になります。

最後に、クエリの最後に Garner のアルゴリズムで答えを復元することが必要であり、これは \(O(\log^2 M)\) 時間かかります。よってクエリごとに合計 \(O(N \log M + \log^2 M)\) 時間かかります。

実装例

C++ (161 ms)