問題概要
整数 $t, m $ が与えられる．
以下の形式の問題が $t$ ケース与えられるので，それぞれ解け：
正整数 $n$ と長さ $n$ の正整数列 $C = \langle C_1, C_2, \dots, C_n \rangle$ が与えられる．以下の条件を満たす数列の個数を $m $ で割った余りを求めよ：
- 数列の要素は $1$ 以上 $n$ 以下の整数．
- 各 $i \in \{ 1, 2, \dots, n \}$ について，数列に含まれる $i$ の個数は $C_i$ 個．
制約
- $1 \leq t \leq 10^5$
- $2 \leq m \leq 10^9$
- $1 \leq n$
- $\forall i \in \{ 1, 2, \dots, n \}, 1 \leq C_i$
- $\sum_{ i - 1 }^n C_i \leq 5{,}000$
- $\text{$t$ 個の問題に渡る $n$ の総和} \leq 3 \times 10^5$
解法
数列の個数そのものはいかにも膨大になりそうです．なので DP のようなことをしたい気もしますが，よくある $1$ 要素ずつ決める DP だと区別するべき状態の個数（各値の残り個数の組合せの数）が膨大になるので厳しいです．
今回は，$1, 2, \dots, n$ のどれでもないてきとーな値（ここでは $0$ で説明します）を $\sum C$ 個並べた長さ $\sum C$ の列から始めて，$0$ を徐々に $1, 2, \dots, n$ で置き換えていくと考えます．このとき，各 $i$ について，$0$ を $i$ で $1$ 個ずつ置き換えるのではなく，$C_i$ 個の $0$ を選んでまとめて $i$ で置き換えると考えます．$C_i$ 個の $0$ の選び方は，残っている $0$ の個数を $k$ として二項係数 $$\binom{ k }{ C_i }$$ になります．$k$ は各段階で置き換え済みの $0$ の個数を $\sum C$ から減じれば出るので，数列 $S$ を
\[
S_i = \begin{cases}
0 & \text{($i = 0$)} \\
S_{ i - 1 } + C_i & \text{($1 \leq i \leq n$)}
\end{cases}
\]
とすれば $$\binom{ S_n - S_{ i - 1 } }{ C_i }$$ となり，数えるべき列の個数は $$\prod_{ i = 1 }^n \binom{ S_n - S_{ i - 1 } }{ C_i }$$ となります．
上記の $S$ は累積和として知られているものです．また，合同式の法が任意に与えられるせいで二項係数の計算に逆元を使う方法は使いづらいです．ここで Pascal の三角形を思い出すと，$\binom r c$ は Pascal の三角形の $r + 1 $ 列目 $c + 1$ 番目の値として現れます．Pascal の三角形は加算のみで計算でき，$\sum C$ の制約が小さいため $\Theta( ( \max( \sum C ) )^2 )$ 時間かけて前計算しておくことができます．これで各ケースを $\Theta( n )$ 時間で解くことができ，全ケースに渡る $n$ の総和の制約から TL に間に合います．
コード
#include <atcoder/modint> using namespace atcoder; using MINT = modint; inline ostream& operator<<( ostream &s, const MINT &t ){ s << t.val(); return s; } // パスカルの三角形による nCr on Z/mZ の計算 // 前処理 \Theta( N^2 ), クエリ O( 1 ) class PascalTriangle; // 中身省略 MINT solve( const auto &nCr ) { IN( int, N ); VI C( N ); cin >> C; VI S( 1 ); partial_sum( ALL( C ), BI( S ) ); MINT res = 1; REP( i, N ) { res *= nCr( S[N] - S[i], C[i] ); } return res; } int main() { IN( int, T, M ); modint::set_mod( M ); PascalTriangle nCr( 5'000, M ); REP( T ) { cout << solve( nCr ) << LF; } cout << flush; return 0; }
