# AGC067D Unique Matching

## 問題

https://atcoder.jp/contests/agc067/tasks/agc067_d

おそらく本質的には想定解と同じだけど違う見方だったのでメモ。

## 解説

条件を満たす区間集合を数えて最後に $N!$ 倍します。

重要な性質として、 $N$ 個の区間 $[L_i,R_i]$ が条件を満たすとき、 $L_i=R_i$ が成り立つ $i$ が存在します。

これは次のように対偶（各区間の長さが $2$ 以上ならばマッチングは $0$ または $2$ 種類以上）を示せます。 $L_i \leq i \leq R_i$ としていいです。各区間の長さは $2$ 以上なので、各 $i$ に対し $L_i \leq a_i \leq i \leq a_i+1 \leq R_i$ が成り立つような $a_i\ (a_i \in \{i-1,i\})$ が取れます。 $1 \leq a_i \leq N-1$ より鳩ノ巣原理から $a_i=a_j$ が成り立つ $i,j\ (i\neq j)$ が存在します。このような $i,j$ に対しては $L_j \leq a_j \leq i \leq a_j+1 \leq R_j$ およびその逆が成り立つことから $i,j$ に対応する区間を入れ替えることができます。以上よりマッチングは存在するならば $2$ 種類以上存在することが示せました。

この性質から、区間集合が unique なマッチングを持つとき、マッチングは以下の手順で得られることが分かります。

1. 集合 $X$ を $X=\{1,2,\dots,N\}$ で初期化する。
2. 以下を $N$ 回行う。 まだマッチしていない区間のうち、 $x \in X$ であって $x \in [L_i,R_i]$ を満たす $x$ がただ一つ存在するようなものを選ぶ（複数ある場合はそのような $x$ が最小であるような区間を選ぶ）。区間と $x$ をマッチさせ、 $X$ から $x$ を除く。

逆にこの手順で得られるマッチングが unique であることは明らかです。以上より上記の手順を最後までやり切れる区間集合の数え上げに帰着されます。

上記の手順で $x$ が $X$ から取り出されたのが $P_x$ 回目であるとして、 $P$ の区間maxに関する cartesian tree を固定します。各ノードには $P_x$ 回目の操作でマッチされた区間 $[L,R]$ が対応します。

$P_x$ 回目の操作でマッチされた区間 $[L,R]$ について、 $L,R$ が満たすべき条件を考えます。まず $x$ の左右の子孫の数 $ls,rs$ について、 $0 \leq x-L\leq ls, 0\leq R-x\leq rs$ が明らかに必要です。そのほかには右の子が $y$ とすると $y \leq R$ が必要です（でなければ $y$ より先に $x$ がマッチされるべきです）。逆にこれらの条件が満たされる場合は区間集合に対して確かにこの cartesian tree が対応します。

以上より

$f[n]:$ $N=n$ のときの答え

$dp[l][r]:$ 根の左右の子のサイズが $l,r$ であるような cartesian tree に対応する区間集合の数

とすると

$dp[l][r] = \sum_{i=0}^{r-1} f[l] \times (l+1) \times dp[i][r-1-i] \times (r-i)$

が成り立ちます。 $f[n]$ のほかに $dp[i][n-i] \times (n-i+1)$ の総和 $g[n]$ も併せて計算すれば $O(N^2)$ 時間で計算できます。さらに式を見ると $dp[l][r]$ は必要ではなく、 $f,g$ についての漸化式で書け、これは分割統治fftで高速化できます。

## 提出

(PyPy 482ms)

https://atcoder.jp/contests/agc067/submissions/57101383