ABC 214G : Three Permutations

問題文：https://atcoder.jp/contests/abc214/tasks/abc214_g

問題概要

日本語なので略。

公式解説を読んでて分からなかったところだったり、自分が類題を解くときにつまづきそうなところだったりをメモがてら書きます。

解法

パート1. 包除原理

$\{1, 2, \ldots, n\}$ の順列全体の集合を $\mathfrak{S}_n$ と書くことにする。この問題の条件を満たす順列全体の集合を $X$ とすると

$X = \{ r \in \mathfrak{S}_n \mid 1 \leq {}^\forall i \leq n, r_i \neq p_i \land \ r_i \neq q_i \}$

となる。

ここで、 $1 \leq i \leq n$ に対して、集合 $\mathcal{A}_i$ を

$\mathcal{A}_i := \{ r \in \mathfrak{S}_n \mid r_i \neq p_i \land r_i \neq q_i \}$

と置くと、 $X = \displaystyle\bigcap_{i = 1}^n {\cal A}_i$ が成立する。

余事象を取ると

$\mathfrak{S}_n \setminus X = \mathfrak{S}_n \setminus \displaystyle\bigcap_{i = 1}^n {\cal A}_i = \displaystyle\bigcup_{i = 1}^n (\mathfrak{S}_n \setminus {\cal A}_i)$

が成り立つ。

ここで、 ${\cal B}_i := {\frak S}_n \setminus {\cal A}_i = \{ r \in {\frak S}_n \mid r_i = p_i \lor r_i = q_i \}$ とおき、要素数に注目すると

$|\mathfrak{S}_n \setminus X| = \left|\displaystyle\bigcup_{i = 1}^n ({\frak S}_n \setminus {\cal A}_i)\right| \iff |{\frak S}_n| - |X| = \left|\displaystyle\bigcup_{i = 1}^n {\cal B}_i\right| \iff |X| = |{\frak S}_n| - \left|\displaystyle\bigcup_{i = 1}^n {\cal B}_i\right|$

が成り立つ。 $\left|\bigcup_{i = 1}^n {\cal B}_i\right|$ の項に対して包除原理を適用することで

$|X| = |{\frak S}_n| - \displaystyle\sum_{\emptyset \neq S \subseteq \{1, 2, \ldots, n\}} (-1)^{|S| - 1} \left|\bigcap_{i \in S} {\cal B}_i\right|$

ここで、 $S \subseteq \{1, 2, \ldots, n\}$ を固定したとき、 $\left|\bigcap_{i \in S} {\cal B}_i\right|$ について考察する。 $\tau \in \bigcap_{i \in S} {\cal B}_i = \{ r \in {\frak S}_n \mid {}^\forall i \in S, r_i = p_i \lor r_i = q_i \}$ を一つとると、 $j \in \{1, 2, \ldots, n\} \setminus S$ を満たす $j$ 同士で自由に $\tau$ の値を入れ替えた順列 $\tau'$ も $\bigcap_{i \in S} {\cal B}_i$ の元となる。したがって、 $|\bigcap_{i \in S} {\cal B}_i|$ は $(n-|S|)!$ の倍数である。

つまるところ、 ${\cal C}_S := \{ (r_i)_{i \in S} \mid {}^\forall i \in S, r_i = p_i \lor r_i = q_i \}$ としたとき、 $\left|\bigcap_{i \in S}{\cal B}_i\right| := (n - |S|)! |{\cal C}_S|$ が成立する。*1

したがって、 $d_i = \displaystyle\sum_{S = \{1, 2, \ldots, n\}, |S| = i} \left|{\cal C}_S\right|$ と置くことで、 $|X| = \displaystyle\sum_{i = 0}^n (-1)^i (n - i)! d_i$ と書ける。よって $i = 0, 1, \ldots, n$ に対して $d_i$ が求められればこの問題を解くことができる。

パート2. 各 $S \subseteq \{1, 2, \ldots, n\}$ に対して $|{\cal C}_S|$ を求める
これは解説に述べられている通りである。 $V = \{1, 2, \ldots, n\}, E = \{(p_i, q_i) \mid i = 1, 2, \ldots, n\}$ からなるグラフ $G=(V, E)$ を考える。すべての頂点の次数が $2$ なので、 $G$ はサイクルと自己ループからなるグラフである。
ここで、グラフ $G_S$ を、辺集合が $E_S = \{ (p_i, q_i) \mid i \in S\}$ 、頂点集合が $E_S$ の端点全体の集合 $\partial E_S$ となるグラフと定義する。 $G_S$ はサイクル、自己ループ、およびパスからなるグラフである。
この記号のもと、 $|{\cal C}_S|$ は $G_S$ の各辺に対して隣接している頂点を割り当てる組み合わせの総数となることに注意する。このとき、任意の $\emptyset \neq S \subseteq \{1, 2, \ldots, n\}$ に対して、以下のように ${\cal C}_S$ が計算できる。

$G_S$ が自己ループのとき、明らかに $|{\cal C}_S| = 1$ 。
$G_S$ がサイクルのとき、サイクルに属する辺のうち 1 本にどの頂点を割り当てるかを決めると自動的に残りの辺の割り当ても決まるため $|{\cal C}_S| = 2$ 。
$G_S$ がパスのとき、どの辺にも割り当てない頂点を 1 つ決めると、すべての辺に対して頂点の割り当てが一意になる。したがって、パスに属する頂点数を $m$ とすると $|{\cal C}_S| = m$ 。
$G_S$ が複数の連結成分から構成される場合、 $|{\cal C}_S|$ はそれぞれの連結成分ごとに上記の通り数の積を求めたもの。

パート3. 複数の $|{\cal C}_S|$ をまとめて求める

パート 2. で求めた $|{\cal C}_S|$ をすべての部分集合について愚直に計算すると ${\rm O}(n2^n)$ 時間かかってしまう。そこで、ひとつの連結成分に含まれる部分グラフ $S$ すべてについて $|{\cal C}_S|$ を効率的に求めることを考える。それぞれの連結成分ごとに $|{\cal C}_S|$ の和を $|S|$ の大きさごとに格納したテーブルを用意できれば、それらのマージは合計 ${\rm O}(n^2)$ 時間でできる。*2

この問題では、部分グラフとしてはサイクルとパスのみを考えれば良い。

$f(m, k) :=$ パスグラフ $P_m = (\{1, 2, \ldots, m\}, \{(i, i + 1) \mid i = 1, 2, \ldots, m - 1\})$ の部分グラフ $P_{m, S}$ のうち、辺集合のサイズが $k$ のものについての $|{\cal C}_S|$ の和 ( $k = 0, 1, \ldots, m - 1$ )
$g(m, k) :=$ サイクルグラフ $Q_m = (\{1, 2, \ldots, m\}, \{(i, i + 1) \mid i = 1, 2, \ldots, m - 1\} \cup \{1, m\})$ の部分グラフ $Q_{m, S}$ のうち、辺集合のサイズが $k$ のものについての $|{\cal C}_S|$ の和 ( $k = 0, 1, \ldots, m$ )

とする。
まず、 $f(m, k)$ は、以下のグラフから $m - 1 - k$ 本の辺を抜いたグラフ(孤立点は無視する)を考えることで、

$f(m, k) = \displaystyle\sum_{i_0 = 0 < i_1 < i_2 < \ldots < i_{m-1-k} < m = i_{m-k}} \prod_{j = 1}^{m-k} (i_j - i_{j-1})$

と書けることがわかる。*3。

f:id:kagamiz:20210821170035p:image:w700:h93 — 辺に番号をつけたパスグラフ

$i'_j = i_j - i_{j-1}$ と置き直すことで、

$f(m, k) = \displaystyle\sum_{i'_1 + i'_2 + \ldots + i'_{m-k} = m, i'_j \geq 1} \prod_{j = 1}^{m-k} i'_j$

と書ける。
ここで、

${\rm dp}\lbrack i \rbrack\lbrack j \rbrack = \displaystyle\sum_{a_1 + a_2 + \ldots + a_i = j, a_k \geq 1}\prod_{k = 1}^i a_k$

と定義すると、 $f(m, k) = {\rm dp}\lbrack m - k \rbrack\lbrack m \rbrack$ である。また、 ${\rm dp}\lbrack 1 \rbrack\lbrack x \rbrack = x$ となることにも留意する。

まず、 $a_i$ の値で場合分けすることにより、 ${\rm dp}\lbrack i \rbrack\lbrack j \rbrack = \displaystyle\sum_{k = 1}^{j - 1} {\rm dp}\lbrack i - 1 \rbrack\lbrack j - k \rbrack \cdot k$ となることがわかる。
また、 ${\rm dp}\lbrack i + 1 \rbrack\lbrack j \rbrack - {\rm dp}\lbrack i \rbrack\lbrack j \rbrack = \displaystyle\sum_{k = 1}^j {\rm dp}\lbrack i - 1 \rbrack\lbrack k \rbrack$ と書けるため、 ${\rm s}\lbrack i\rbrack\lbrack j\rbrack = \displaystyle\sum_{k = 1}^j {\rm dp}\lbrack i \rbrack\lbrack k \rbrack$ という累積和テーブルを ${\rm dp}$ テーブルと一緒に計算することで、 ${\rm dp}\lbrack i \rbrack\lbrack j \rbrack$ は $(i, j)$ の昇順で計算することで各要素あたり ${\rm O}(1)$ 時間で計算できる。これで $f(m, k)$ は効率的に計算することができる。

$g(m, k)$ については、 $g(m, m) = 2$ であることはパート 2. で確認済みである。 $k < m$ のとき、 $Q_{m, S}$ はいくつかのパスから成るグラフである。 $Q_m$ の各辺に下図のように番号を振って、取り除かれた辺のうち最小のものに対する $f(\cdot, \cdot)$ の定義式の $i'_1$ の値で場合分けをすることにより、