题解 P6295 【有标号 DAG 计数】
ix35
·
·
题解
弱连通有标号 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)} 分别解决掉就可以了。
另一个 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 被我吃了。
```cpp
#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;
}
```