循環するケース
ある順列の１番目とn番目が隣接し、循環している場合のDPに関してまとめる。
問題
- ABC285 E - Work or Rest
- 過去にやってた
- ABC307 E - Distinct Adjacent
- 循環の起点となる1番目だけ注目し、１番目と同じかどうかの２パターンの個数を考えることで簡単にしている。
- i-1番目が1番目と同じ → i番目はm-1とりうる
- i-1番目が1番目と同じでない → 1番目と同じはとれないかつ隣と同じ数字はとれないのでi番目はm-2とりうる
- 循環の起点となる1番目だけ注目し、１番目と同じかどうかの２パターンの個数を考えることで簡単にしている。