环上计数+计数转概率：ABC318EX

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132650494

https://atcoder.jp/contests/abc318/tasks/abc318_h

先转为概率， $f_i$ 表示 $i$ 个点两人都AC的概率， $g_i$ 表示恰好一个人AC的概率。

两个人都AC，只能为全部自环， $f_i=\frac 1 {i!}$

现在求 $g_n$ 。然后有个定理， $n$ 个点形成的图形， $n$ 所在的环的大小在 $[1,n]$ 内随机生成。（很好证明）

然后考虑枚举 $n$ 所在的环大小为 $i$ ，先考虑由 $f$ 推向 $g$ 的情况。剩下 $n-i$ 个点两个人都AC，所以为 $f_{n-i}$ 。那么当前这个环只能有一个人AC，所以环大小至少为2。

此时谁AC都可以，所以最小的那条边有两个选择，即 $\frac 2 i$ 。因此 $f\to g$ 的答案为：

$$\Large g_n=\frac{\sum_{i=2}^n\frac 2 if_{n-i}}n$$

现在考虑 $g\to g$ 的贡献。之后的贡献为 $g_{n-i}$ 。发现他已经保证了恰好一个人AC，而且已经确定了这个人是谁。那么当前这个环的选择唯一，但大小可以使1，因为即使两个人在这个环内同时AC也无所谓。

$$\Large g_n=\frac{\sum_{i=1}^n\frac 1 ig_{n-i}}n$$

结合起来就是：

$$\Large g_n=\frac{\sum_{i=1}^n(\frac 2 if_{n-i}\small{(i\ne 1)}\Large+\frac 1 ig_{n-i})}n$$

令 $a_i=\frac 2 i$ 且 $a_1=0$ ， $b_i=\frac 1 i$

然后上面就变成了：

$$\Large g_n=\frac{\sum_{i=1}^n(a_if_{n-i}+b_ig_{n-i})}n$$

前面NTT，后面是个分治NTT即可。