题目链接

题解

给出若干个完全图，然后完全图之间首尾相连并成环，要求删边使得两点之间路径数不超过\(1\)，求方案数

容易想到各个完全图是独立的，每个完全图要删成一个森林，其实就是询问\(n\)个点有标号森林的个数

设\(f[i]\)表示\(i\)个点有标号森林的个数

枚举第一个点所在树大小，我们只需求出\(n\)个点有多少种树，由\(purfer\)序容易知道是\(n^{n - 2}\)

那么有

\[f[n] = \sum\limits_{i = 1}^{n} {n - 1 \choose i - 1}i^{i - 2}f[n - i]\]

化简一下：

\[f[n] = (n - 1)!\sum\limits_{i = 1}^{n}\frac{i^{i - 2}}{(i - 1)!} \times \frac{f[n - i]}{(n - i)!}\]

分治\(NTT\)即可

每个完全图的方案是\(f[a[i]]\)，中间相连的\(n\)条边有\(2^n\)种方案，由乘法原理乘起来即可

但是这样求出来的不是答案，会多算一类情况：

每个完全图的\(1\)和\(a_i\)相通且所有中介边存在

所以我们还需要计算\(g[i]\)表示\(i\)个点的森林，\(1\)和\(i\)点在同一棵树内的方案数

显然

\[g[n] = \sum\limits_{i = 2}^{n} {n - 2 \choose i - 2}i^{i - 2}f[n - i]\]

化简得

\[g[n] = (n - 2)!\sum\limits_{i = 2}^{n} \frac{i^{i - 2}}{(i - 2)!} \times \frac{f[n - i]}{(n - i)!}\]

\(NTT\)即可

最后答案减去\(g[a[i]]\)的乘积即可

复杂度\(O(nlog^2n)\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include