DP を経由せず多項式を利用して数えます。

各文字 \(i\) の個数が丁度 \(a_i\) 個であるような文字列の個数は多項係数 \(\displaystyle \binom{a_1+a_2+\cdots+a_{26}}{a_1, a_2, \ldots, a_{26}}=\dfrac{(a_1+a_2+\cdots+a_{26})!}{a_1!\times a_2!\times \cdots \times a_{26}!}\) なので答えは \(\displaystyle \sum_{l=1}^K l!\lbrack x^l \rbrack\prod_{i=1}^{26}\left(\sum_{j=0}^{C_i}\dfrac{1}{j!}x^j\right)\) と表せます。ここで \(\lbrack x^l\rbrack f(x)\) は多項式 \(f\) の \(l\) 次の係数です。

従って \(\displaystyle\prod_{i=1}^{26}\left(\sum_{j=0}^{C_i}\dfrac{1}{j!}x^j\right)\) の \(K\) 次以下の部分を計算できればよいですが、 これは \(O(\sigma K ^ 2)\) 時間で可能です。また、多項式乗算に FFT を利用すれば \(O(\sigma K\log K)\) 時間に削減されます (公式解説の DP もFFT を用いた畳み込みで同様の計算時間が達成されます)。 なお \(\sigma\) は文字種数であり、本問では \(\sigma=26\) に固定されています。