随笔题解 Pb. 8

AtCoder Grand Contest 065 D. Not Intersect

史诗题目，震撼我的大脑和小脑。

试图挑战时隔已久的 AGC，结果被 A 题当头棒喝（悲

单位圆上分布着 $N$ 个可区分的标记点。试在这些标记点之间连恰好 $M$ 条边，且任意两条不同的边在除去标记点之外的地方不相交，这样的方案数。对 $10^9 + 7$ 取模。

$1 \leqslant N \leqslant 10^7$，$0 \leqslant M \leqslant N (N - 1) / 2$。

$\mathtt{3s/1024MB}$。

$N \leqslant 2$ 直接打表。

对于 $N \geqslant 3$ 的情况，我们令 $a_{n, m}$ 表示在题设条件上再追加「圆上相邻的标记点之间不连边」，这样的在 $n$ 个标记点之间连 $m$ 条边的方案数。令

$$f_n = \sum_{m \geqslant 0} a_{n + 3, m} y^m$$ $$F = \sum_{n \geqslant 0} f_n x^n$$

最终我们需要的答案是 $[x^{N - 2}] [y^M] {(1 + y)}^N F$。

对于

$${(1 + y)}^{n + 3} f_n$$

考虑连到 $1$ 号标记点的边，可以分为以下几种情况：

$1$ 号标记点不和其他标记点连边：

那么我们将其无视即可。这部分的方案数为

$${(1 + y)}^{n + 2} f_{n - 1}$$

和 $1$ 号标记点连边的标记点中，标号最小的是 $2$ 号：

那么只需要标记 $(1, 2)$ 必选即可。这部分的方案数为

$$y {(1 + y)}^{n + 2} f_n$$

和 $1$ 号标记点连边的标记点中，标号最小的是 $3$ 号：

考虑相邻边，那么除去 $(1, 2)$ 以外的 $n + 2$ 条相邻边还都可以连；考虑非相邻边，那么相当于孤立 $2$ 号标记点之后剩下的 $n + 2$ 个标记点之间连边。再算上必选的 $(1, 3)$，得到这部分的方案数为

$$y {(1 + y)}^{n + 2} f_{n - 1}$$

和 $1$ 号标记点连边的标记点中，标号最小的是 $n + 3$ 号：

那么只需标记 $(1, n + 3)$ 必选，然后孤立 $1$ 号标记点即可。这部分的方案数为

$$y {(1 + y)}^{n + 2} f_{n - 1}$$

和 $1$ 号标记点连边的标记点中，标号最小的是 $i$ 号（$4 \leqslant i \leqslant n + 2$）：

相当于将整个圆分成了两部分：左半部分共 $i - 1$ 个标记点；右半部分共 $(n + 3) - (i - 1) + 1 = n - i + 5$ 个标记点。再算上必选的 $(1, i)$，得到这部分的方案数为

$$[y^m] {(1 + y)}^{i - 1} f_{i - 4} \times y {(1 + y)}^{n - i + 4} f_{n - i + 2}$$

整理一下上面的柿子，我们可以得到

$$f_n = (1 + 2y) f_{n - 1} + y (1 + y) \sum_{i = 0}^{n - 2} f_i \times f_{n - i - 2}$$

也就是说

$$F = 1 + x (1 + 2y) F + x^2 y (1 + y) F^2$$

这是一个关于 $F$ 的一元二次方程。根据 $[x^0] F = 1$，我们可以解得（当然这个柿子我是抄的官方题解）

$$F = \frac{(1 - x - 2xy) - (1 - x) \sqrt{1 - \frac{4xy}{(1 - x)^2}}}{2xy (1 + y)}$$

然后我们看到一坨很丑陋的柿子

$$\sqrt{1 - \frac{4xy}{(1 - x)^2}}$$

根据官方题解给出的奇妙结论

$$[x^n] [y^m] \sqrt{1 - \frac{4xy}{(1 - x)^2}} = [x^n] \frac{x^m}{(1 - x)^{2m}} \cdot [y^m] \sqrt{1 - 4y} = - \frac{2}{2m - 1} \frac{(n + m - 1)!}{(n - m)! (m - 1)! m!}$$

那么我们预处理以下阶乘和阶乘逆元就可以 $\Theta(1)$ 求单个 $[x^n] [y^m] F$ 了。

最终答案就是 $[x^{N - 2}] [y^M] {(1 + y)}^N F$。枚举两部分 $y$ 的次数就可以 $\Theta(N)$ 求了。

数学，妙不可言。

……什么，你问我说不应该是 $[x^{N - 3}]$ 吗？

不是很懂，反正我按照 $[x^{N - 2}]$ 求是对的，按照 $[x^{N - 3}]$ 求是错的。官方题解写的也是前者。