自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:19:26，当前版本为作者最后更新于2020-04-06 16:00:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

弱连通有标号 DAG 计数

考虑先求出任意有标号 DAG，然后对 EGF 求一下 $\ln$ 即可得到弱连通的 DAG 数量。

设 $f(i)$ 表示 $i$ 个点的有标号 DAG 数量，则：

$$f(i)=\sum\limits_{j=1}^i \binom{i}{j}\times (-1)^{j+1}\times f(i-j)\times 2^{j(i-j)} $$

其中 $j$ 表示入度为 $0$ 的点的个数（因为 DAG，所以一定存在至少一个入度为 $0$ 的点），剩余的 $i-j$ 个点构成 DAG，这 $j$ 个点到另外 $i-j$ 个点任意选择连不连边，但是注意到这个 $j$ 没有保证恰好，只是保证最少有 $j$ 个入度为 $0$ 的点，所以还需要容斥一下。

然后把 $\binom i j$ 和 $2^{j(i-j)}$ 分别解决掉就可以了。

$\binom i j$ 我们再熟悉不过，求两边的 EGF 即可消去。

另一个 trick 也是常用的：

$$j\times (i-j)=\binom i 2-\binom j 2-\binom {i-j} 2 $$

所以:

$$2^{j(i-j)}=\dfrac{2^{\binom i 2}}{2^{\binom j 2}\times 2^{\binom{i-j} 2}} $$

按照和 EGF 相同的策略，我们设两个生成函数：

$$F(x)=\sum\limits_{i=0}^{+\infty}\dfrac{f_i}{i!\times 2^{\binom i 2}}x^i $$$$G(x)=\sum\limits_{i=0}^{+\infty}\dfrac{(-1)^{i+1}}{i!\times 2^{\binom i 2}}x^i $$

那么改写最上面的式子，就有：

$$F(x)=F(x)G(x)+1$$

最后的 $+1$ 是因为 $f_0=1$。

解得：

$$F(x)=\dfrac{1}{1-G(x)}$$

计算可得 $F(x)$ 的值。

最后考虑弱连通的条件，不弱连通的 DAG 肯定由若干个连通分量组合，设弱连通 DAG 的 EGF 为 $H(x)$，那么按照 EGF 的组合意义：

$$F'(x)=\exp(H(x))$$

其中 $F'(x)$ 是 $f_i$ 的 EGF。

所以：

$$H(x)=\ln(F'(x))$$

总的过程是一次求逆和一次 $\ln$，时间复杂度 $O(n\log n)$。

程序里 qpow 被我吃了。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=400010,P=998244353;
int n,cur,lim,l,g,invg,r[MAXN],fac[MAXN],inv[MAXN];
int a[MAXN],b[MAXN],c[MAXN],d[MAXN],e[MAXN],h[MAXN],tmp[MAXN];
void deri (int n,int a[],int b[]) {
	for (int i=0;i<=n-2;i++) {b[i]=(1ll*a[i+1]*(i+1))%P;}
	b[n-1]=0;
	return;
}
void itr (int n,int a[],int b[]) {
	for (int i=n-1;i>=1;i--) {b[i]=(1ll*a[i-1]*qpow(i,P-2))%P;}
	b[0]=0;
	return;
}
void ntt (int a[],int lim,int type) {
	for (int i=0;i<lim;i++) {
		if (r[i]>i) {swap(a[i],a[r[i]]);}
	}
	for (int i=1;i<lim;i<<=1) {
		int wn=qpow(type==1?g:invg,(P-1)/(i<<1));
		for (int j=0;j<lim;j+=(i<<1)) {
			int wnk=1;
			for (int k=0;k<i;k++) {
				int x=a[j+k],y=(1ll*wnk*a[j+k+i])%P;
				a[j+k]=(x+y)%P,a[j+k+i]=(x-y+P)%P;
				wnk=(1ll*wnk*wn)%P;
			}
		}
	}
	return;
}
void getinv (int n,int a[],int b[]) {
	if (n==1) {b[0]=qpow(a[0],P-2);return;}
	getinv((n+1)>>1,a,b);
	lim=1,l=0;
	while (lim<(n<<1)) {lim<<=1,l++;}
	for (int i=0;i<lim;i++) {r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));}
	for (int i=0;i<n;i++) {tmp[i]=a[i];}
	for (int i=n;i<lim;i++) {tmp[i]=0;}
	ntt(tmp,lim,1),ntt(b,lim,1);
	for (int i=0;i<lim;i++) {b[i]=(1ll*((2ll-(1ll*tmp[i]*b[i])%P+P)%P)*b[i])%P;}
	ntt(b,lim,-1);
	int inv=qpow(lim,P-2);
	for (int i=0;i<lim;i++) {b[i]=(1ll*b[i]*inv)%P;}
	for (int i=n;i<lim;i++) {b[i]=0;}
	return;
}
void mul (int lim,int c[],int d[],int e[]) {
	for (int i=0;i<lim;i++) {r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));}
	ntt(c,lim,1),ntt(d,lim,1);
	for (int i=0;i<lim;i++) {e[i]=(1ll*c[i]*d[i])%P;}
	ntt(e,lim,-1);
}
void getln (int n,int a[],int b[]) {
	deri(n,a,c);
	getinv(n,a,d);
	lim=1,l=0;
	while (lim<(n<<1)) {lim<<=1,l++;}
	mul(lim,c,d,e);
	int inv=qpow(lim,P-2);
	for (int i=0;i<lim;i++) {e[i]=(1ll*e[i]*inv)%P;}
	for (int i=n;i<lim;i++) {e[i]=0;}
	itr(n,e,b);
	return;
}
int main () {
	scanf("%d",&n);
	fac[0]=inv[0]=1;
	for (int i=1;i<=n;i++) {fac[i]=(1ll*fac[i-1]*i)%P;}
	inv[n]=qpow(fac[n],P-2);
	for (int i=n-1;i>=1;i--) {inv[i]=(1ll*inv[i+1]*(i+1))%P;}
	for (int i=1;i<=n;i++) {
		a[i]=(1ll*inv[i]*qpow(qpow(2,(1ll*i*(i-1)/2)),P-2))%P;
		if (i&1) {a[i]=(P-a[i])%P;}
	}
	a[0]=1;
	g=3,invg=qpow(3,P-2);
	getinv(n+1,a,b);
	for (int i=0;i<=n;i++) {b[i]=(1ll*((1ll*b[i]*fac[i])%P)*qpow(2,(1ll*i*(i-1)/2)))%P;}
	for (int i=0;i<=n;i++) {b[i]=(1ll*b[i]*inv[i])%P;}
	getln(n+1,b,h);
	for (int i=1;i<=n;i++) {
		printf("%d\n",(1ll*h[i]*fac[i])%P);
	}
	return 0;
}