题解

对于图上一个点 $v$，考虑设它的相邻点依次为 $v_1,v_2,\cdots,v_m$,那么必然有 $m$ 为偶数。

于是可以考虑把 $v$ 删掉，然后整个多边形上剩下的点会按顺序被 $v_1,v_2,v_3,\cdots,v_m$ 划分为若干块，而 $v_1$ 和 $v_n$ 一定在两端所以会划为 $m-1$ 块。

剩下的边只会出现在块内。对于第一块，会发现 $v_1$ 在块内的边的数量为奇数，而中间的点度数不变，所以 $v_2$ 在第一块内的边的数量为奇数。继而 $v_2$ 在第二块内的边的数量为偶数，于是可以推出 $v_3$ 在第二块内的边的数量为偶数……

所以奇数位的块是个有欧拉回路的三角剖分图，偶数位的块是奇度数点在多边形上相邻的有欧拉路的三角剖分图。为了方便可以直接钦定 $1$ 号点被删。

于是还要考虑对第二种情况的图进行计数。钦定两个奇度数点中的一个像上面一样删掉即可。

所以有转移方程：

$$f_i =\sum\limits_{|S|\bmod2=1\wedge\sum\limits_{j=0}^{|S|-1}(S_j-1)=i-2}\prod\limits_{j=0}^{|S|-1}([2\nmid j]f_{S_j}+[2\mid j]g_{S_j}) $$$$g_i =\sum\limits_{|S|\bmod2=0\wedge\sum\limits_{j=0}^{|S|-1}(S_j-1)=i-2}\prod\limits_{j=0}^{|S|-1}([2\nmid j]f_{S_j}+[2\mid j]g_{S_j}) $$

写成 OGF：

$$F(x) =\sum\limits_{i=0}f_ix^i, G(x) =\sum\limits_{i=0}g_ix^i $$

于是：

$$F(x) =x^2\sum\limits_{i=0}(x^{-1}F(x))^i(x^{-1}G(x))^{i+1} =\frac{xG(x)}{1-x^{-2}F(x)G(x)} $$$$G(x) =x^2\sum\limits_{i=0}(x^{-1}F(x))^i(x^{-1}G(x))^i =\frac{x^2}{1-x^{-2}F(x)G(x)} $$

根据第一个方程：

$$G(x) =x^2\frac{F(x)}{F^2(x)+x^3}$$

根据第二个方程：

$$F(x) =x^2\frac{G(x)-x^2}{G^2(x)}$$

如果观察样例或者表就会发现 $f_i$ 只有在 $3\mid i$ 时非零，$g_i$ 只有在 $i\bmod3=2$ 时非零，所以可以设 $F(x)=F_0(x^3),G(x)=x^2G_0(x^3)$：

$$x^2G_0(x^3) =G(x) =x^2\frac{F(x)}{F^2(x)+x^3} =x^2\frac{F_0(x^3)}{F_0^2(x^3)+x^3} $$$$F_0(x^3) =F(x) =x^2\frac{G(x)-x^2}{G^2(x)} =x^2\frac{x^2G_0(x^3)-x^2}{x^4G_0^2(x^3)} $$

令 $x^3=y$ 则有:

$$G_0(y) =\frac{F_0(y)}{F_0^2(y)+y}, F_0(y) =\frac{G_0(y)-1}{G_0^2(y)} $$

这个除 $3$ 优化也可以用在朴素 $O(n^2)$ 做法上，如果你的常数足够厉害那么可能可以借此跑过 70pts。

事实上简化 dp 时或者大力化简式子后可以得到：

$$F_0(y) =yG_0^2(y)$$

组合意义是在删掉一条多边形的边后，整个图形分为两个仅有一个公共点的块，每个块恰好是 $g_i$ 所计的合法块。

最后就是要解这个方程：

$$yG_0^4(y)-G_0(y)+1 =0$$

牛顿迭代即可。

第二问只需枚举图上的边的两边的图的大小，会发现答案就是：

$$\sum\limits_{i=0}^n(i-2)(n-i)f_ig_{n-i+2}$$

所以卷积即可。总复杂度 $O(n\log n)$。