AtCoder Beginner Contest 234 F 問題 Reordering
問題
提出解答
問題の概要
から連続とは限らず1文字以上抜き出した後, 並び替えることでできる文字列はいくつか?
制約
は英小文字からなる文字列
解法
で英小文字全体の集合とし,
と文字列
に対して
で
に含まれる
の数とする.
非空文字列 が作成可能であることの必要十分条件は,
任意の に対して,
である.
に対して, 和と順序, 重さを
に対して,
と定義する.
すると, 問題は として,
となる非空文字列の数
を求めることになる.
となる
の個数を
と置くと,
である.
を固定し,
について考える. これは
である.
であるようなものをまとめると,
であるが, これを多項式の係数とみなすと, 各 に対して,
とおくと,
よって, 求めるべき正解は