yukicoder No. 1392 - Don't be together

• 問題
• AC

スターリング数のような設定（ボールは区別できる、箱は区別できない、各箱に1つ以上のボールが入る）の数え上げはスターリング数のようなDPができる、という典型を思い出す。

とりあえずスターリング数と同じように$f(x, y) := 1, 2, ..., x$を$y$個のグループにわける場合の数、と定める。$P_x < x$の場合はスターリング数と同じような遷移^[1] $f(x, y) = f(x-1, y-1) + (y-1)f(x-1, y)$が成立しそうだが、$x < P_x$だと$P_x$の所属するグループに関する未来の情報が必要でうまくいかない。DPするにはもう少し変数を増やす必要がある。

与えられるのは順列なので巡回置換に分解してみる。整数の順序は関係ないので、$(1 2 3 4)(5 6)(7 8 9)$のように各巡回置換が連続区間に対応しているものだけ考えればよい。このとき、$f$を次のように定義すればDPできる:

$f(x, y, z) := 1, 2, ..., x$を$y$個のグループにわけるとして、$x$が$x$の属する巡回置換の先頭の整数と同じグループに属する$(z=1)$か異なるグループに属する$(z=0)$場合の数。

---

1. 遷移の意味付けはdrkenさんの記事を参照。 ↩︎