题目传送门

题目大意

给出\(n\)，求出\(n\)个点的图满足该图为一个点双连通分量的方案数。

前置知识

• 拓展拉格朗日反演

• 多项式指数函数、对数函数

思路

如果做过有标号无向连通图计数就最好了。

我们来重温一下，我们设有标号无向图的指数生成函数为\(F(x)\)，可以得到:

这里的\(2^{\binom{i}{2}}\)就是每条边要或者不要。

我们再设有标号无向连通图的指数生成函数为\(G(x)\)，可以得到:

我们现在再设\(D(x)\)为有标号有根无向连通图，可以得到:

我们再设\(b_i\)为\(i\)个点的无根点双联通分量的个数，我们可以得到：

感性理解就是说，一个有标号有根无向连通图我们把根所在的点双提出来，上面每个点对应了一个连通块的根，除以\(i!\)是因为图是不讲顺序的。

如果我们设：

那我们就可以得到：

这里的\(D^{-1}(x)\)是指的\(D(x)\)的复合逆函数，即:

我们设\(H(x)=\ln \frac{D(x)}{x}\)，可以得到:

这里使用拓展拉格朗日反演公式可以得到：

这里使用多项式快速幂公式就可以得到：

于是，我们就可以在\(\Theta(n\log n)\)的时间复杂度内解决这个问题了。不过不知道为什么我的常熟异常的大，开了\(\text {O}_2\)还没有别人不开\(\text {O}_2\)跑得快。为我自己默哀。。。

\(\text {Code}\)

        #include <bits/stdc++.h>
using namespace std;

#define Int register int
#define mod 998244353
#define Gii 332748118
#define ll long long
#define MAXN 600005
#define Gi 3

int quick_pow (int a,int b){
	int res = 1;for (;b;b >>= 1,a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod;
	return res;
}

int limit,l,r[MAXN];

void NTT (int *a,int type){
	for (Int i = 0;i < limit;++ i) if (i < r[i]) swap (a[i],a[r[i]]);
	for (Int mid = 1;mid < limit;mid <<= 1){
		int Wn = quick_pow (type == 1 ? Gi : Gii,(mod - 1) / (mid << 1));
		for (Int R = mid << 1,j = 0;j < limit;j += R){
			for (Int k = 0,w = 1;k < mid;++ k,w = 1ll * w * Wn % mod){
				int x = a[j + k],y = 1ll * w * a[j + k + mid] % mod;
				a[j + k] = (x + y) % mod,a[j + k + mid] = (x + mod - y) % mod;
			}
		}
	} 
	if (type == 1) return ;
	int Inv = quick_pow (limit,mod - 2);
	for (Int i = 0;i < limit;++ i) a[i] = 1ll * a[i] * Inv % mod;
}

int c[MAXN];

void Solve (int len,int *a,int *b){
	if (len == 1) return b[0] = quick_pow (a[0],mod - 2),void ();
	Solve ((len + 1) >> 1,a,b);
	limit = 1,l = 0;
	while (limit < (len << 1)) limit <<= 1,l ++;
	for (Int i = 0;i < limit;++ i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
	for (Int i = 0;i < len;++ i) c[i] = a[i];
	for (Int i = len;i < limit;++ i) c[i] = 0;
	NTT (c,1);NTT (b,1);
	for (Int i = 0;i < limit;++ i) b[i] = 1ll * b[i] * (2 + mod - 1ll * c[i] * b[i] % mod) % mod;
	NTT (b,-1);
	for (Int i = len;i < limit;++ i) b[i] = 0;
}

void deravitive (int *a,int n){
	for (Int i = 1;i <= n;++ i) a[i - 1] = 1ll * a[i] * i % mod;
	a[n] = 0;
}

void inter (int *a,int n){
	for (Int i = n;i >= 1;-- i) a[i] = 1ll * a[i - 1] * quick_pow (i,mod - 2) % mod;
	a[0] = 0;
}

int b[MAXN];

void Ln (int *a,int n){
	memset (b,0,sizeof (b));
	Solve (n,a,b);deravitive (a,n);
	while (limit <= n) limit <<= 1,l ++;
	for (Int i = 0;i < limit;++ i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
	NTT (a,1),NTT (b,1);
	for (Int i = 0;i < limit;++ i) a[i] = 1ll * a[i] * b[i] % mod;
	NTT (a,-1),inter (a,n);
	for (Int i = n + 1;i < limit;++ i) a[i] = 0;
}

int F0[MAXN];

void Exp (int *a,int *B,int n)
{
	if (n == 1) return B[0] = 1,void ();
	Exp (a,B,(n + 1) >> 1);
	for (Int i = 0;i < limit;++ i) F0[i] = B[i];
	Ln (F0,n);
	F0[0] = (a[0] + 1 + mod - F0[0]) % mod;
	for (Int i = 1;i < n;++ i) F0[i] = (a[i] + mod - F0[i]) % mod;
	NTT (F0,1);NTT (B,1);	
	for (Int i = 0;i < limit;++ i) B[i] = 1ll * F0[i] * B[i] % mod;
	NTT (B,-1);
	for (Int i = n;i < limit;++ i) B[i] = 0;
}

int read ()
{
	int x = 0;char c = getchar();int f = 1;
	while (c < ‘0‘ || c > ‘9‘){if (c == ‘-‘) f = -f;c = getchar();}
	while (c >= ‘0‘ && c <= ‘9‘){x = (x << 3) + (x << 1) + c - ‘0‘;c = getchar();}
	return x * f;
}

void write (int x)
{
	if (x < 0){x = -x;putchar (‘-‘);}
	if (x > 9) write (x / 10);
	putchar (x % 10 + ‘0‘);
}

int fac[MAXN],caf[MAXN],lim = 3e5;

void init (){
	fac[0] = 1;for (Int i = 1;i <= lim;++ i) fac[i] = 1ll * fac[i - 1] * i % mod;
	caf[lim] = quick_pow (fac[lim],mod - 2);for (Int i = lim;i;-- i) caf[i - 1] = 1ll * caf[i] * i % mod;
} 

int H[MAXN],H_[MAXN],G[MAXN],FG[MAXN];

void prepare (){
	int len = 1 << 17,lll = 17;
	for (Int i = 0;i < len;++ i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << lll - 1);
	for (Int i = 0;i < len;++ i) H[i] = 1ll * quick_pow (2,1ll * i * (i - 1) / 2 % (mod - 1)) * caf[i] % mod;
	Ln (H,len - 1);
	for (Int i = 0;i < len;++ i) H[i] = 1ll * H[i + 1] * (i + 1) % mod;H[len - 1] = 0;
	Ln (H,len - 1);
	for (Int i = 0;i < len;++ i) H_[i] = H[i];limit = 1 << 18,l = 18;
	for (Int i = 0;i < limit;++ i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
	deravitive (H_,len - 1),NTT (H_,1); 
}

void work (int n){
	if (!(-- n)) return puts ("1"),void ();
	limit = 1 << 17,l = 17;
	memset (F0,0,sizeof (F0)),memset (FG,0,sizeof (FG));
	for (Int i = 0;i < limit;++ i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
	for (Int i = 0;i < limit;++ i) G[i] = 1ll * H[i] * (mod - n) % mod;
	Exp (G,FG,1 << 17),limit = 1 << 18,l = 18;
	for (Int i = 0;i < limit;++ i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
	NTT (FG,1);for (Int i = 0;i < limit;++ i) FG[i] = 1ll * FG[i] * H_[i] % mod;NTT (FG,-1); 
	write (1ll * FG[n - 1] * fac[n - 1] % mod),putchar (‘\n‘);
}

signed main(){
	init (),prepare ();
	for (Int i = 1;i <= 5;++ i) work (read ());
	return 0;
}

    

原文：https://www.cnblogs.com/Dark-Romance/p/13285081.html