模板多项式 exp

ABC387G

求 \(n\) 个点，每个回路长度都是质数的有标号无向连通图个数。

首先回路之间肯定点不相交，否则若长度为 \(a,b\) 的两个点相交回路有 \(k\) 条公共边，则形成一个长度为 \(a+b-2k\) 的回路，

而 \(a+b-2k\) 肯定是偶数且不是 \(2\)，它肯定不是质数。所以把回路缩起来之后，合法的图一定是一棵树。

设图中有 \(m\) 个回路，第 \(i\) 个回路长度为 \(s_i\)，则把它们连成树的方案数为 \(n^{m-2}\prod s_i=\dfrac{\prod ns_i}{n^2}\)。（扩展 Cayley 定理）

问题转化为对于每种把点集连成若干个回路的方案，求 \(\prod ns_i\) 之和除以 \(n^2\)。

考虑列出一个回路的 EGF \(F(x)\) 再 SET 构造（exp），

可以发现对于素数 \(i\)，把 \(i\) 个点连成长度为 \(i\) 的回路有 \(\dfrac{(i-1)!}2\) 种方案，每种方案的权值都是 \(ni\)，

特别地，把 \(1\) 个点连成长度为 \(1\) 的回路有 \(1\) 种方案，其权值为 \(n\)，

所以 \(F(x)=nx+\sum\limits_{i\ge 3,i\in\mathbf P}\dfrac n2x^i\)，答案即为 \(\left[\dfrac{x^n}{n!}\right]\exp F(x)\)。