問題概要
正整数 $k$ と長さ $26$ の非負整数列 $C = \langle C_1, C_2, \dots, C_{ 26 } \rangle$ が与えられる．英大文字からなる長さ $1$ 以上 $k$ 以下の文字列であって，辞書式順序で $i$ ($1 \leq i \leq 26$) 番目の文字の出現回数が $C_i$ 個以下であるようなものの個数を $\bmod { 998{,}244{,}353 }$ で求めよ．
制約
- $1 \leq k \leq 1000$
- $0 \leq C_i \leq 1000$
解法
$\bmod$ に関する部分は適切に処理するなり AtCoder Library (ACL) を使うなりすればよいので割愛します．
空文字列から始めてより長い文字列を順に構築していく方向で考えます．一文字ずつ（末尾に）追加しようとすると最大 $26$ 択の選択肢が最大 $1000$ 回あってやばいです．これを回避するために，文字種ごとにまとめて挿入することを考えます．つまり，辞書順で $i$ 番目までの文字からなる文字列の個数から $i + 1$ 番目までの文字からなる文字列の個数を計算しようと試みます．
$i$ 番目までの文字からなる長さ $l$ の文字列があるとします．ここに $i + 1$ 番目の文字を $j$ 個挿入して，$i + 1$ 種類目までの文字からなる長さ $l + j$ の文字列を作ることを考えます．長さが $l$ なことから，$i + 1$ 種類目の文字を挿入できる箇所は，文字列の両端を含めて $l + 1$ 箇所あります．そのそれぞれに $i + 1$ 種類目の文字を $0$ 個以上挿入し，かつ挿入個数の総和が $C_{ i + 1 }$ 個以下になっていれば，欲しい値が求まることになります．これは，長さ $l + 1$ の非負整数列であって総和が $C_{ i + 1 }$ 以下であるようなものの個数に一致するので，そういう数列の個数が分かっていれば，$i + 1$ 番目の文字を挿入する個数を固定した場合に構成できる新たな文字列の個数を計算することができます．列の個数の計算は後回しにして，一旦
\begin{equation*}
P_{ m, s } := \text{項数 $m $ で総和が $s$ な非負整数列の個数}
\end{equation*}
としておきます．これを用いれば解きたい問題について漸化式を立てることができて，
\begin{equation*}
dp_2[i][l] := \begin{cases}
1 & \text{($i = 0, l = 0$)} \\
0 & \text{($i = 0, 1 \leq l$)} \\
dp_2[ i - 1 ][ l - j ] \times P_{ l - j + 1, j } & \text{($1 \leq i, j \leq C_i, 0 \leq l - j$)} \\
0 & \text{(otherwise)}
\end{cases}
\end{equation*}
となります*1．
では $P$ の計算はどうやるのかというと，こちらも DP で求めることができます．気持ちとしては一個の $0$ のみからなる列から出発して，
- 列の末尾要素に $1$ を足す．
- 列の末尾に新たな要素として $0$ を追加する．
というふたつの操作で列を作ります．漸化式を立てるならば……，と思ったのですが，こちらはいわゆる「配る DP」スタイルでいきます．初期状態は上記の通り
\begin{equation*}
dp_1[i][j] = \begin{cases}
1 & \text{($i = 1, j = 0$)} \\
0 & \text{(otherwise)}
\end{cases}
\end{equation*}
となります．遷移は，各 $dp_1[i][j]$ から
\begin{align*}
dp_1[i][ j + 1 ] &\overset{+}{\leftarrow} dp_1[i][j] && \text{（末尾要素に $1$ を足す）} \\
dp_1[ i + 1 ][j] &\overset{+}{\leftarrow} dp_1[i][j] && \text{（末尾に $0$ を連結する）}
\end{align*}
となります*2．
これで必要な値の計算方法が揃ったので，答えを出すことができます．計算量についてですが，アルファベットサイズを定数とするならば，$dp_1$ の計算には $\Theta( k \max{ C } )$ 時間がかかり，$dp_2$ の計算は，$O( k^2 )$ 時間がかかります．どちらも十分に発散が遅いので，問題を解くことができます．
コード
#include <atcoder/modint> using namespace atcoder; using MINT = modint998244353; int main() { IN( int, K ); VI C( 26 ); cin >> C; static MINT part[ 1024 ][ 1024 ]; // part[ # of boxes ][ divided integer ] := ways part[1][0] = 1; REP( i, 1001 ) { REP( j, 1001 ) { part[i][ j + 1 ] += part[i][j]; part[ i + 1 ][j] += part[i][j]; } } static MINT dp[ 1024 ]; // dp[ length ] := ways dp[0] = 1; REP( i, 26 ) { for ( int j = 1000; 0 <= j; --j ) { for ( int k = 1; k <= C[i] && j + k <= K; ++k ) { dp[ j + k ] += dp[j] * part[ j + 1 ][k]; } } } cout << accumulate( begin( dp ) + 1, begin( dp ) + K + 1, MINT() ).val() << endl; return 0; }
