P6295 有标号 DAG 计数

· · 题解

先来看个弱化版的题目：

BZOJ2863

就是这道题的题目，只是不需要弱联通，还有数据范围在 3000。

怎么做？

有向无环图有一个经典的处理方式，就是拓扑排序，每次找出入度为 0 的点。

对于这些入度为 0 的点，删掉仍然还是一个 DAG。因此我们可以枚举入度为零个数至少为 i 的点的数量，我们可以得出：

f_i=\sum\limits_{j=1}^n (-1)^{j+1}f_{i-j}\times 2^{j(i-j)}\times \dbinom ij

其中 2^{j(i-j)} 是因为入度为 0 可以和其他点任意连边（注意是至少），(-1)^{j+1} 是因为至少，是容斥。\dbinom nm 就是选择，我觉得这里问题都不大。

然后就是，这个式子要 O(nlogn) 处理出来。

这里赠送一个技巧：ab=\dbinom {a+b}2-\dbinom a2-\dbinom b2。证明很简单。

这个有什么用呢？就是把 a\times b 分成 a+b,a,b 有关的式子，特别是在幂中实用，就是需要把乘法拆开的时候。

那么有：

f_i=\sum\limits_{j=1}^n(-1)^{j+1}f_{i-j}\times \dfrac{2^{\binom i2}}{2^\binom j22^\binom {i-j}2}\times \dfrac{i!}{j!(i-j)!}

将跟 i,j,i-j 有关的整理好，得：

\dfrac{f_i}{2^{\binom i2}i!}=\sum\limits_{j=1}^n\dfrac{(-1)^{j+1}}{j!2^\binom{j}{2}}\times \dfrac{f_{i-j}}{2^{\binom {i-j}2}(i-j)!}

这不久好起来了，这不就好起来了？

令生成函数 F(x)=\sum\limits_{i=0}^{\infty}\dfrac{f_i}{2^{\binom i2}i!}x^i,G(x)=\sum\limits_{i=0}^{\infty}\dfrac{(-1)^{i+1}}{i!2^\binom{i}{2}}。

那么有：F(x)=F(x)G(x)+1。

等一下，为什么是这样的，理论上来说多项式乘法不应该下标从 0 开始的吗？

注意：当 j=0 的时候，f_{i-j}=f_i 这一项应该不存在，那么就特殊处理 g_0=0 以抵消这一项，再用多项式乘法，这样就对了。

还有为什么加一，因为 f 的通项公式是建立在 i\ge 1 的情况下的，f_0=1 这个也是特殊情况，常数项加上去。

那么就可以解了，解得：F(x)=\dfrac{1}{1-G(x)}。

你以为这就结束了那你就错了，还有一个任务没完成，F(x) 是可以不弱联通的，但是题目要求必须弱联通。

其实这个很好想到（不就是城市规划吗），一般图一定是弱连通图的 exp，因为你可以把图分成若干个点集，然后这些点集的弱连通图方案数的乘积。

这不就是裸的 EGF 意义上的 e^x 吗？分成若干点集弱连通图方案乘积？那么 F(x)=e^{H(x)},H(x)=Ln(F(x))，注意一定要先转 EGF 再求 Ln。

时间复杂度 O(nlogn)。

Code:

#include<bits/stdc++.h>
#define I inline
#define RI register int
#define rep(i,a,b) for(RI i=a;i<=b;++i)
#define dow(i,a,b) for(RI i=a;i>=b;--i)
using namespace std;
const int N=4e5+5,mo=998244353;
I int add(int a,int b){ return a+b>=mo?a+b-mo:a+b; }
I int sub(int a,int b){ return a-b<0?a-b+mo:a-b; }
I int mul(int a,int b){ return (long long)a*b%mo; }
I int fast(int a,int b=mo-2){ RI res=1;while(b) b&1&&(res=mul(res,a)),a=mul(a,a),b>>=1; return res; }
int n,frac[N],ifac[N],r[N],a[N],b[N],c[N],d[N],e[N],f[N];
I void NTT(int a[],int lim,int op){
    rep(i,1,lim-1) if(r[i]>i) swap(a[i],a[r[i]]);
    for(RI i=1;i<lim;i<<=1){
        RI now=fast(op==1?3:332748118,(mo-1)/(i<<1));
        for(RI j=0;j<lim;j+=(i<<1)){
            RI res=1;
            rep(k,0,i-1){
                RI x=a[j+k],y=mul(res,a[j+k+i]);
                a[j+k]=add(x,y),a[j+k+i]=sub(x,y),res=mul(res,now);
            }
        }
    }
    RI now=fast(lim);
    if(op==-1) rep(i,0,lim-1) a[i]=mul(a[i],now);
}
I void Inv(int a[],int b[],int n){
    if(n==1) return b[0]=fast(a[0]),void(); Inv(a,b,n+1>>1);
    RI lim=1,cnt=0;while(lim<=(n<<1)) lim<<=1,++cnt;rep(i,1,lim-1) r[i]=r[i>>1]>>1|(i&1)<<cnt-1;
    rep(i,0,n-1) c[i]=a[i];rep(i,n,lim-1) c[i]=0;NTT(c,lim,1),NTT(b,lim,1);
    rep(i,0,lim-1) b[i]=mul(b[i],sub(2,mul(c[i],b[i])));NTT(b,lim,-1);rep(i,n,lim-1) b[i]=0;
}
I void Ln(int a[],int b[],int n){
    rep(i,0,n-2) d[i]=mul(a[i+1],i+1);Inv(a,f,n);
    RI lim=1,cnt=0;while(lim<=(n<<1)) lim<<=1,++cnt;rep(i,1,lim-1) r[i]=r[i>>1]>>1|(i&1)<<cnt-1;
    NTT(d,lim,1),NTT(f,lim,1);rep(i,0,lim-1) b[i]=mul(d[i],f[i]);NTT(b,lim,-1);
    dow(i,n-1,1) b[i]=mul(b[i-1],fast(i));b[0]=0;
}
int main(){
    scanf("%d",&n),frac[0]=1;rep(i,1,n) frac[i]=mul(frac[i-1],i);ifac[n]=fast(frac[n]);dow(i,n-1,0) ifac[i]=mul(ifac[i+1],i+1);
    a[0]=1;rep(i,1,n) a[i]=mul(fast(fast(2,1ll*i*(i-1)/2%998244352)),ifac[i]),i&1&&(a[i]=mo-a[i]);
    Inv(a,e,n+1);rep(i,1,n) e[i]=mul(e[i],fast(2,1ll*i*(i-1)/2%998244352));Ln(e,b,n+1);
    rep(i,1,n) printf("%d\n",mul(frac[i],b[i]));return 0;
}