JPSTR

2 secs 1024 MB

｛母音,子音,n｝に分けて考えます。母音の個数を $V$ 、n の個数を $N$ とします。また、それぞれの配置における制限は以下の通りです。

最終的には、各 $a \ (0 \le a \le V)$ についての

$\{$ 母音を合計 $a$ 個並べる通り数 $\}\times\{$ 各母音の直前に $1$ 個以下ずつ合計 $a$ 個以下の子音を挿入する通り数 $\}\times\{$ 文字列の先頭と各母音の直後に合計 $N$ 個以下の n を挿入する通り数 $\}$

の総和が計算できれば良いです。各項は独立に考えてもよく、それらは以下のように計算できます。

第 $1$ 項
- $vow_{i,j}=\{i\ (0 \le i \le 5)$ 種類目の母音まで見て、母音を合計 $j\ (0 \le j \le V)$ 個並べる通り数 $\}$
を順に計算しておきます。遷移の際には、同じものを含む順列を考慮してそれぞれの個数の階乗で割ることを忘れないようにしつつ、畳み込みを使用することで十分高速に求められます。
第 $2$ 項

基本的には第 $1$ 項と同様です。ある母音の直前に子音を追加しないことを表す「 $6$ 種類目の子音」を疑似的に考えて
- $con_{i,j}=\{i\ (0 \le i \le 6)$ 種類目の子音まで見て、子音を合計 $j\ (0 \le j \le V)$ 個並べる通り数 $\}$
を順に計算しておきます。「 $6$ 種類目の子音」を無視すれば、 $con_{6,a}$ は $\{$ 各母音の直前に $1$ 個以下ずつ合計 $a$ 個以下の子音を挿入する通り数 $\}$ に対応します。
第 $3$ 項

「文字列の先頭と各母音の直後」にあたる場所は合計 $a+1$ 個あります。そこに置かれた n は文字列に挿入しないことを追加しないことを表す「廃棄置場」を疑似的に考えると、 $\{a+2$ 箇所に合計 $N$ 個の n を挿入する通り数 $\}$ が求められれば良いです。これは $\{a+1$ 個の仕切りと $N$ 個のボールを一列に並べる通り数 $\}$ に対応するため、 ${}_{a+1+N}\mathrm{C}_N$ です。