ABC213 F-H 個人的メモ

厳密性には欠ける可能性あり　数式はあまり使わないように（めんどくさいし、僕も分からなくなってしまうので） 公式解説にかなり丸投げをしますし、そもそもあまり人に読ませることを想定していないので、ご了承・・・

F

問題文を読むと、いかにも ACL を使いそうな雰囲気
atcoder/string を見てみると、Suffix Array と LCP Array が何か使えそう。

Suffix Array：i 文字目から後ろの文字列（これを Suffix と呼ぶ）というのを考えたときに、辞書順になるような index の配列 LCP Array：文字列とその Suffix Array を考えたときに、隣り合っている文字列同士の先頭何文字が被っているかみたいなのを記録する配列

ここで一つ重要な性質として以下がある： 3つの文字列を辞書順で並べたときに の順だったとすると、

これは が の前何文字かをそのままに後ろをどう更新したか、あるいは が の前何文字かをそのままに後ろをどう更新したか、みたいなのを考えると直感的に納得がいく気がする。
これを一般化すると、任意の2つの Suffix の LCP というのは、Suffix Array で考えたときのその間の LCP の min であるということが分かる。
これを図にすると最大長方形っぽいやつに帰着できるので、stack でごにょごにょすると、できる（この辺りは、公式解説の動画の方を見ると分かる）（丸投げ！）

G

制約的に、見るからに bit DP
dp[S]: ちょうど連結成分の部分集合が S になっているようなのがあるグラフの通り数
とすれば、これは頂点集合が S であるようなグラフの全体から、頂点集合が S であってそれが連結成分にならないようなものを引けばいいので、解説に書いてあるような式が立つ（丸投げ）
求める値は部分集合に頂点 1 と頂点 i を含むような部分集合の dp に、補集合は何でもいいので、2^{補集合の辺の本数} をかけた値の総和（ちょうど、という風にしていることで上手く区別ができている）

H

どんな遷移も左から右に遷移している、というのがミソで、自分からの遷移が出る、ということは自分への遷移はもうない、ということになる。
こういう場合の時は分割統治というのが使えるらしい（公式解説の動画がかなり分かりやすいので、それを見た方が早い気がする・・・）
遷移式を見ると、添え字の和の部分が一定の積の和となっていて、これはいかにも FFT
畳み込みというと嫌な気持ちになるけど、積の和というとそうでもない気がする（僕だけ？）
あとは、これを実装する　実装は公式解説の動画を見ると完全理解ができる（嘘かも）