No.171

文字列 $s$ があるとき, ここに $s$ に含まれない文字 $c$ を $n$ 個追加したときの組み合わせの数を考える. これは, 挿入箇所が $\lvert s \rvert + 1$ 個ありそこに $n$ 個の文字を振り分ける組み合わせの数である.

$i$ 個の挿入箇所に $j$ 個の文字を振り分ける組み合わせの数を $C(i, j)$ とすると,

$$C(i, j) = C(i - 1, j) + C(i - 1, j - 1) + C(i - 1, j - 2)\cdots$$

s.t.

$$C(1, *) = 1$$

となる. ここで,

$$C(i - 1, j - 1) + C(i - 1, j - 2) + \cdots = C(i, j - 1)$$

であるので,

$$C(i, j) = C(i - 1, j) + C(j, i - 1)$$

となる. これを DP で計算する.

あとはすべてのアルファベットで順に計算すればいい.