解法メモ AtCoder Grand Contest 045 D - Lamps and Buttons

解説は包除が出てくるので、違う解き方っぽいです。
（何で包除で解けるか理解できていないので、ほんとに違うか分かりませんが・・・）

問題文：[AGC045D](https://atcoder.jp/contests/agc045/tasks/agc045_d)

---

# 最適なすぬけくんの行動について

最初に点灯しているランプ1～Aを、aと呼ぶことにする。
aはA個ある。
残りの消灯しているランプをbと呼ぶことにする。
bはB個あるとする。$B=N-A$である。

このゲームでは、aの中で$p_i=i$であるようなボタンiを選んでしまうと、
ランプiが消灯し、二度とランプiを点灯できないので、
すぬけくんの負けが確定する。
$p_i=i$なるボタンiを選ぶ確率を最小にするのが最適な行動になる。

順列はランダムなので、
最初にすぬけくんが押すのはボタン1であるとしてよい。
この時、$p_1=1$だと負けが確定。
それ以外の場合、$p_1=i$とすると、
ランプiが点灯または消灯する。
これを見て、ボタンiが安全である($p_i=i$であることはあり得ない)と分かる。
次は(ランプiを点灯させた上で)ボタンiを押すのが最適。
これを繰り返せば、
安全なままたくさんのボタンを押し続けることができる。

しかし、巡回してランプ1に戻ってくると、
次に安全であることが分かっているボタンはないので、
賭けに出るしかない。
残っているボタンが安全である確率は等しいので、
番号最小のボタンを選択することにする。
これを繰り返しているうちに、
全てのbを点灯できればすぬけくんの勝ち。
途中で$p_i=i$なボタンを押したらすぬけくんの負け・・・**(敗北条件1)**。
また、aを全て押した後で、
まだ点灯していないbが残っていてもすぬけくんの負け・・・**(敗北条件2)**。

# 選択する順に並べ直す

ここで、考えやすくするために、
すぬけくんがボタンを選択する順に順列を並べ直したものを考える。
並べるのは押したボタン番号ではなく、
ランプ番号の方(iではなく$p_i$)。
勝ち負けとランプの点灯消灯を一旦無視し、
最後まで「ルール」通りボタンを押し続けるものとする。
つまり、

```
ボタン1から始めて順に押す
→ 巡回して1に戻ってきたら、残りの中の最小を選択
→ 順に押す
→ 巡回して戻ってきたら、残りの中の最小を選択
→ ・・・
```

を最後まで繰り返す。
並べ直した順列をQとすると、
QからPを復元できるので、PとQは一対一対応している。
Pの代わりにQを考えてよい。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/605081/e5bec90e-e59a-c57d-14ea-f7901cd7fba8.png)

Qを1つ定めると、すぬけくんの勝ち負けが定まる。
よって、$N!$通りのQのうち、
すぬけくんが勝つQの個数（を$10^9+7$で割った余り）が、
求める答である。

# 勝つQの並べ方は？

Qは上の図のように、巡回する単位で分けることができる。
巡回する単位をサイクルと呼ぶことにする。
上図では、サイクルごとに色分けしている。

下図は、番号を消し、aを黄色、bを灰色で表したQの例である
（上図とは別のQの例）。
隙間が空いているところはサイクルの切れ目である。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/605081/4d1ed128-f78e-e817-cbcc-b9322b22267a.png)

**敗北条件2**を避けるためには、
最後のaより右にbがあってはいけない。
ということは、各サイクルの末尾は必ずaである。

また、**敗北条件1**の$p_i=i$なボタンは長さ1のサイクルに相当する。
**敗北条件1**を避けるためには、
長さ1のサイクルに出会う前に全てのbを点灯させる必要がある。
つまり、長さ1のサイクルがある場合、
そこより右にbがあってはいけない。（上図は右にbがあるのでNGな例）

逆に、以上を満たせば、必ずすぬけくんの勝ちになる。

# 勝つQを数え上げる

## aに注目
aは最大5000個だが、bは1千万個弱存在し得る。
bを順々に扱うようなアルゴリズムは無理そうなので、
後で計算で一気に処理できることを期待し、
順列Qからbを除きaだけ残した順列Rを考えてみる(下図)。
QからRに変わることで、長さ1のサイクルが増える。
Rにおける長さ1のサイクルを「孤独なa」と呼ぶことにする（下図の「孤」）。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/605081/96a43680-5690-34f5-c6c7-a8263ef96ca0.png)

Rにbを挿入して勝つQを作ることを考える。
bを挿入できる場所はA+1箇所あるが、
右端は**敗北条件2**を満たしてしまうので、
それ以外のA箇所(図の↑印)。
勝つQになるのは、挿入方法が以下の2つのいずれかを満たす場合である。

- (1) 全ての孤独なaの左隣にbが1つ以上入ること
- (2) 孤独なaの左隣にbが1つもない場所（「超孤独なa」と呼ぶ）があったら、全てのbがそこより左にあること

この2つは、それぞれ以下の通り数え上げることができる。
先に(2)から考える。

## (2)の数え方

最も左にある超孤独なaの位置をiとする。
(2)を満たすためには、以下2点を満たすことが必要十分。

- 全てのbが超孤独なa（下図の「超」）より左になければならない
- iより左にある孤独なaは、その左隣にbが1つ以上必要(**敗北条件1**を避けるため)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/605081/aa32aaf5-8890-c922-b40b-9ab8b2783a6b.png)

このような並べ方を数えるにあたり、
まずa, bを並べ、その後で番号を付けると考える。

### a, bの並べ方を数える

まず、番号なしで、aとbの並べ方を数える。
孤独なaの左隣（上図＋印）にbを1つ入れ、孤独なaと抱き合わせて考えると、
残ったbはi箇所ある隙間に自由に入れられるので、
以下の重複組み合わせで数えられる。jは孤独なaの数。

```math
{}_{i}{H}_{B-j}
```

jを決め打てば数えられることが分かる。

### 番号の付け方を数える

次にa, bに番号をつける方法を数える。
bは何の制約もないので、B!通り。
aへの番号の付け方は、

`dp[i][j]`: 位置iの手前でサイクルが切れ、かつそこまでに孤独なaがj個ある並べ方

が分かれば、

$dp[i][j]$  ×（超孤独なaの並べ方）×（残りの並べ方は制約なし）
＝ $dp[i][j] * 1 * (A-i-1)!$

で数えられる。
dpの添え字にjを入れたのは、
jを決め打たないと先ほどの重複組合せが計算できないため。

まとめると、
最も左にある超孤独なaの位置がi、
それより左にある孤独なaがj個の時、
並べ方は

```math
{}_{i}H_{B-j} * dp[i][j] * (A-i-1)! * B!
```

通り。
これをi, jについて全て足せばよく、$O(A^2)$で計算できる。

## (1)の数え方

`dp[i=A][j]`を使えば、(2)と同様の考え方で、

```math
aとbの並べ方={}_{A}H_{B-j}
```

```math
番号の付け方=dp[A][j] * B!
```

なので、まとめると、

```math
{}_{A}H_{B-j} * dp[A][j] * B!
```
通り。
これをjについて全て足せばよく、$O(A)$で計算できる。

残るは`dp[i][j]`の数え方。

## `dp[i][j]`の数え方
`dp[i][j]`は以下の通り分解できる。

```
dp[i][j]
＝(はじめのi個が1つのサイクル)
 ＋(位置1の手前で切れ、続くi-1個が1つのサイクル)
 ＋(位置2の手前で切れ、続くi-2個が1つのサイクル)
 ・・・
 ＋(位置kの手前で切れ、続くi-k個が1つのサイクル)
 ・・・
 ＋(位置i-2の手前で切れ、続く2個が1つのサイクル)
 ＋(位置i-1の手前で切れ、次が孤独なa)
```

位置kの手前で切れる並べ方は、`dp[k][j]`。(j:孤独なaの数)
但しk=i-1の時は、次が孤独なaなのでjが1つ増える。よって`dp[k][j-1]`。

続くi-k個のaが切れずに1つのサイクルになる並べ方は、
最後(位置i-1)は1通り(戻るための番号は1つに決まっている)で、
それ以外の場所は、
残ったA-k-1個のaからi-k-1個を任意に並べてよい。
よって

```math
{}_{A-k-1}P_{i-k-1}
```

通り。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/605081/9d27301f-4892-d4f0-8f35-5215c608cf8c.png)

以上をまとめると、`dp[i][j]`は以下のとおり漸化式で表せる。

```math
dp[i][j] = \sum_{k=0}^{i-2} \left( dp[k][j] * {}_{A-k-1}P_{i-k-1}\right) + dp[i-1][j-1]
```

これをそのまま計算すると、$O(A^3)$かかってしまう。
$\sum$の部分を毎回計算せず、再利用できないか・・・と考えると、
ちゃんと`dp[i-1][j]`を計算する時の$\sum$から
計算できるようになっている。
$\sum$の部分を`S[i][j]`、`S[i-1][j]`として、
結果だけ示すと、以下のように計算できる。

```math
S[i][j] ＝ { S[i-1][j] + dp[i-2][j] } * (A-i+1)
```

これで$O(A^2)$で計算できる。
このまま計算してもよさそうだが、
Sを元の式に代入して消去し、dpだけの漸化式にしてもよい。

以上で、勝つQの並べ方を(1)と(2)に分けて全て数え上げることができた。

---

考察に1日半、実装に3時間かかりました。
どのような並べ方を数えればよいかは早い段階でまとまりましたが、
具体的な数え方がどうにもまとまらず悩みました。
コンテスト中に解けるようになってみたい。