Preface
带标号的DAG计数，陈指导最近出了一道最基础的，发现好久没用过生成函数那一类的了就来看看
DAG的定义相信都不同多说了，以下默认对(998244353)取模
有标号的DAG计数I
Pro：求(n)点带标号的DAG的数目，不强制联通，(nle 5000)
Sol：显然考虑(O(n^2))，设(f_i)表示答案，我们每次枚举DAG中入度为(0)的点的数目(j)
此时图被拆成了两个部分，前面的(j)个点只能向后面的(i-j)个点连边，而后面的(i-j)个点可以随便连
但我们仔细一想后面的点随便连并不保证入度为(0)的点只有前面的(j)个，因此要容斥一下：
[f_i=sum_{j=1}^i (-1)^{j-1} imes C_i^j imes 2^{j(i-j)} imes f_{i-j}
]
#include<cstdio>
#define RI register int
#define CI cosnt int&
using namespace std;
const int N=5005,mod=998244353;
int n,C[N][N],f[N],pw[N*N];
int main()
{
RI i,j; for (scanf("%d",&n),C[0][0]=i=1;i<=n;++i)
for (C[i][0]=C[i-1][0],j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
for (pw[0]=i=1;i<=n*n;++i) pw[i]=2LL*pw[i-1]%mod;
for (f[0]=i=1;i<=n;++i) for (j=1;j<=i;++j)
{
int ret=1LL*pw[j*(i-j)]%mod*C[i][j]%mod*f[i-j]%mod;
if (j&1) (f[i]+=ret)%=mod; else (f[i]+=mod-ret)%=mod;
}
return printf("%d",f[n]),0;
}
有标号的DAG计数II
Pro：求(n)点带标号的DAG的数目，不强制联通，(nle 100000)
Sol：显然考虑化式子然后用多项式来做，我们发现这个式子中有一个(j(i-j))的项涉及了(ij)，显然我们要想办法把它拆成可以独立算的
[j(i-j)=frac{i^2}{2}-frac{j^2}{2}-frac{(i-j)^2}{2}
]
由于(2)在模(998244353)意义下存在二次剩余，然后再拆一下组合数移个项：
[frac{f_i}{i! imes sqrt 2^{i^2}}=sum_{j=1}^i frac{(-1)^{j-1}}{j! imes sqrt 2^{j^2}} imes frac{f_{i-j}}{(i-j)! imes sqrt 2^{(i-j)^2}}
]
显然令(F(x)=sum_{i=0}^n frac{f_i}{i! imes sqrt 2^{i^2}} x^i,G(x)=sum_{i=1}^nfrac{(-1)^{i-1}}{i! imes sqrt 2^{i^2}} x^i)
则有(F(x)=G(x)F(x)+1)，故(F(x)=frac{1}{1-G(x)})
多项式求逆即可，复杂度(O(nlog n))
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=998244353,r2=882049182;
int n,fact[N],invf[N],f[N<<2],g[N<<2],ir2;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline int sum(CI x,CI y)
{
int t=x+y; return t>=mod?t-mod:t;
}
inline int sub(CI x,CI y)
{
int t=x-y; return t<0?t+mod:t;
}
inline void init(CI n)
{
RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
for (invf[n]=quick_pow(fact[n]),i=n-1;~i;--i) invf[i]=1LL*invf[i+1]*(i+1)%mod;
}
namespace Poly
{
int B[N<<2],rev[N<<2],lim,p;
inline void NTT(int *f,CI opt)
{
RI i,j,k; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
for (i=1;i<lim;i<<=1)
{
int D=quick_pow(3,~opt?(mod-1)/(i<<1):mod-1-(mod-1)/(i<<1));
for (j=0;j<lim;j+=(i<<1))
{
int W=1; for (k=0;k<i;++k,W=1LL*W*D%mod)
{
int x=f[j+k],y=1LL*f[i+j+k]*W%mod;
f[j+k]=sum(x,y); f[i+j+k]=sub(x,y);
}
}
}
if (!~opt)
{
int Div=quick_pow(lim); for (i=0;i<lim;++i) f[i]=1LL*f[i]*Div%mod;
}
}
inline void init(CI n)
{
for (lim=1,p=0;lim<=n;lim<<=1,++p);
for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);
}
inline void get_inv(int *A,int *G,CI n)
{
if (n==1) return (void)(G[0]=quick_pow(A[0]));
RI i; for (get_inv(A,G,n+1>>1),init(n<<1),i=0;i<n;++i) B[i]=A[i];
for (NTT(G,1),NTT(B,1),i=0;i<lim;++i)
G[i]=1LL*sub(2,1LL*G[i]*B[i]%mod)*G[i]%mod;
for (NTT(G,-1),i=n;i<lim;++i) B[i]=G[i]=0;
}
};
int main()
{
RI i; for (scanf("%d",&n),i=g[0]=1,ir2=quick_pow(r2),init(n);i<=n;++i)
g[i]=1LL*(i&1?mod-1:1)*invf[i]%mod*quick_pow(ir2,1LL*i*i%(mod-1))%mod;
return Poly::get_inv(g,f,n+1),printf("%d",1LL*f[n]*quick_pow(r2,1LL*n*n%(mod-1))%mod*fact[n]%mod),0;
}
有标号的DAG计数III
Pro：求(n)点带标号的DAG的数目，要求弱联通，(nle 5000)
Sol：同样先考虑(O(n^2))的做法，这部分的答案(g_i)显然就是在(f_i)上减去不连通的方案数
我们考虑包含(1)的弱联通DAG的大小，然后转移：
[g_i=f_i-sum_{j=1}^{i-1} C_{i-1}^j imes f_j imes g_{i-j}
]
#include<cstdio>
#define RI register int
#define CI cosnt int&
using namespace std;
const int N=5005,mod=998244353;
int n,C[N][N],f[N],g[N],pw[N*N];
int main()
{
RI i,j; for (scanf("%d",&n),C[0][0]=i=1;i<=n;++i)
for (C[i][0]=C[i-1][0],j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
for (pw[0]=i=1;i<=n*n;++i) pw[i]=2LL*pw[i-1]%mod;
for (f[0]=i=1;i<=n;++i) for (j=1;j<=i;++j)
{
int ret=1LL*pw[j*(i-j)]%mod*C[i][j]%mod*f[i-j]%mod;
if (j&1) (f[i]+=ret)%=mod; else (f[i]+=mod-ret)%=mod;
}
for (i=1;i<=n;++i) for (g[i]=f[i],j=1;j<i;++j)
(g[i]+=mod-1LL*C[i-1][j]*f[j]%mod*g[i-j]%mod)%=mod;
return printf("%d",g[n]),0;
}
有标号的DAG计数IV
Pro：求(n)点带标号的DAG的数目，要求弱联通，(nle 100000)
Sol：同上化一化式子，容易得到：
[frac{g_i}{(i-1)!}=frac{f_i}{(i-1)!}-sum_{j=1}^{i-1} frac{f_j}{j!} imes frac{g_{i-j}}{(i-j-1)!}
]
设(F(x)=sum_{i=1}^n frac{f_i}{i!} x^i,G(x)=sum_{i=1}^n frac{g_i}{(i-1)!} x^i,H(x)=sum_{i=1}^n frac{f_i}{(i-1)!} x^i)
则有(G(x)=H(x)-F(x)G(x))，故(G(x)=frac{H(x)}{1+F(x)})
再次上多项式求逆即可，复杂度(O(nlog n))
PS：还有一种看起来很优美的指数型生成函数并利用多项式求$ln $的做法，可惜我策不懂的说
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=998244353,r2=882049182;
int n,fact[N],invf[N],f[N<<2],g[N<<2],h[N<<2],t[N<<2],ir2,lim;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline int sum(CI x,CI y)
{
int t=x+y; return t>=mod?t-mod:t;
}
inline int sub(CI x,CI y)
{
int t=x-y; return t<0?t+mod:t;
}
inline void init(CI n)
{
RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
for (invf[n]=quick_pow(fact[n]),i=n-1;~i;--i) invf[i]=1LL*invf[i+1]*(i+1)%mod;
}
namespace Poly
{
int B[N<<2],rev[N<<2],lim,p;
inline void NTT(int *f,CI opt)
{
RI i,j,k; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
for (i=1;i<lim;i<<=1)
{
int D=quick_pow(3,~opt?(mod-1)/(i<<1):mod-1-(mod-1)/(i<<1));
for (j=0;j<lim;j+=(i<<1))
{
int W=1; for (k=0;k<i;++k,W=1LL*W*D%mod)
{
int x=f[j+k],y=1LL*f[i+j+k]*W%mod;
f[j+k]=sum(x,y); f[i+j+k]=sub(x,y);
}
}
}
if (!~opt)
{
int Div=quick_pow(lim); for (i=0;i<lim;++i) f[i]=1LL*f[i]*Div%mod;
}
}
inline void init(CI n)
{
for (lim=1,p=0;lim<=n;lim<<=1,++p);
for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);
}
inline void get_inv(int *A,int *G,CI n)
{
if (n==1) return (void)(G[0]=quick_pow(A[0]));
RI i; for (get_inv(A,G,n+1>>1),init(n<<1),i=0;i<n;++i) B[i]=A[i];
for (NTT(G,1),NTT(B,1),i=0;i<lim;++i)
G[i]=1LL*sub(2,1LL*G[i]*B[i]%mod)*G[i]%mod;
for (NTT(G,-1),i=n;i<lim;++i) B[i]=G[i]=0;
}
};
int main()
{
RI i; for (scanf("%d",&n),i=g[0]=1,ir2=quick_pow(r2),init(n);i<=n;++i)
g[i]=1LL*(i&1?mod-1:1)*invf[i]%mod*quick_pow(ir2,1LL*i*i%(mod-1))%mod;
for (Poly::get_inv(g,f,n+1),i=0;i<=n;++i)
f[i]=1LL*f[i]*quick_pow(r2,1LL*i*i%(mod-1))%mod*fact[i]%mod;
for (i=0;i<=n;++i) h[i]=1LL*f[i]*invf[i-1]%mod,f[i]=1LL*f[i]*invf[i]%mod;
for (lim=1;lim<=(n<<1);lim<<=1); for (i=n+1;i<lim;++i) f[i]=0;
for (i=0;i<lim;++i) Poly::B[i]=0; Poly::get_inv(f,t,n+1); Poly::init(n<<1);
for (Poly::NTT(h,1),Poly::NTT(t,1),i=0;i<lim;++i)
h[i]=1LL*h[i]*t[i]%mod; Poly::NTT(h,-1);
return printf("%d",1LL*h[n]*fact[n-1]%mod),0;
}
Postscript
数数题真是有趣呢