点击刷新
\(\text{Problem}:\)有标号 DAG 计数
\(\text{Solution}:\)
设 \(F(x)\) 表示有标号 DAG 的 \(\text{EGF}\)，\(G(x)\) 表示弱连通的有标号 DAG 的 \(\text{EGF}\)，有：
\[F(x)=\sum\limits_{i=0}^{\infty}\cfrac{G^{i}(x)}{i!}=e^{G(x)}\\
G(x)=\ln F(x)
\]
设 \(f_{i}\) 表示 \(F(x)\) 第 \(i\) 项的系数。设 \(a_{i,j}\) 表示 \(i\) 个点恰好有 \(j\) 个入度为 \(0\) 的方案数，\(b_{i,j}\) 表示 \(i\) 个点钦定 \(j\) 个点入度为 \(0\) 的方案数，有：
\[\begin{aligned}
b_{i,j}&=\sum\limits_{k=j}^{i}\binom{k}{j}a_{i,k}\\
a_{i,j}&=\sum\limits_{k=j}^{i}(-1)^{k-j}\binom{k}{j}b_{i,k}
\end{aligned}
\]
考虑 \(f_{i}\) 的 \(dp\) 转移式，有：
\[\begin{aligned}
f_{i}&=\sum\limits_{j=1}^{i}a_{i,j}\\
b_{i,j}&=\binom{i}{j}\cdot2^{j(i-j)}\cdot f_{i-j}
\end{aligned}
\]
现在把 \(a_{i,j}\) 用 \(b_{i,j}\) 替换，有：
\[\begin{aligned}
f_{i}&=\sum\limits_{j=1}^{i}\sum\limits_{k=j}^{i}(-1)^{k-j}\binom{k}{j}\binom{i}{k}\cdot 2^{k(i-k)}\cdot f_{i-k}\\
&=\sum\limits_{k=1}^{i}\binom{i}{k}\cdot 2^{k(i-k)}\cdot f_{i-k}\sum\limits_{j=1}^{k}(-1)^{k-j}\binom{k}{j}\\
&=\sum\limits_{k=1}^{i}(-1)^{k-1}\binom{i}{k}\cdot 2^{k(i-k)}\cdot f_{i-k}
\end{aligned}
\]
考虑把 \(nk\) 拆成卷积形式，有：
\[f_{i}=i!\cdot 2^{\frac{i^2}{2}}\sum\limits_{j=1}^{i}\frac{(-1)^{j-1}\cdot 2^{-\frac{j^2}{2}}}{j!}\cdot\frac{2^{-\frac{(i-j)^2}{2}}\cdot f_{i-j}}{(i-j)!}\\
A(x)=\sum\limits_{i=0}^{\infty}\frac{f_{i}\cdot x^{i}}{i!\cdot 2^{\frac{i^2}{2}}}\\
B(x)=\sum\limits_{i=1}^{\infty}\frac{(-1)^{i-1}\cdot x^{i}}{i!\cdot 2^{\frac{i^2}{2}}}\\
A(x)=A(x)B(x)+1\\
A(x)=\frac{1}{1-B(x)}
\]
利用多项式求逆可以求出 \(A(x)\)，从而求出 \(F(x)\)，再利用多项式 \(\ln\) 即可求出 \(G(x)\)。时间复杂度 \(O(n\log n)\)。
\(\text{Code}:\)
#include <bits/stdc++.h>
#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=265010, Mod=998244353;
inline int read()
{
int s=0, w=1; ri char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int n;
int rev[N],r[24][2],fac[N+5],inv[N+5];
inline int ksc(int x,int p) { int res=1; for(;p;p>>=1, x=1ll*x*x%Mod) if(p&1) res=1ll*res*x%Mod; return res; }
inline void Get_Rev(int T) { for(ri int i=0;i<T;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?(T>>1):0); }
inline void DFT(int T,vector<int> &s,int type)
{
for(ri int i=0;i<T;i++) if(rev[i]<i) swap(s[i],s[rev[i]]);
for(ri int i=2,cnt=1;i<=T;i<<=1,cnt++)
{
int wn=r[cnt][type];
for(ri int j=0,mid=(i>>1);j<T;j+=i)
{
for(ri int k=0,w=1;k<mid;k++,w=1ll*w*wn%Mod)
{
int x=s[j+k], y=1ll*w*s[j+mid+k]%Mod;
s[j+k]=(x+y)%Mod;
s[j+mid+k]=x-y;
if(s[j+mid+k]<0) s[j+mid+k]+=Mod;
}
}
}
if(!type) for(ri int i=0,inv=ksc(T,Mod-2);i<T;i++) s[i]=1ll*s[i]*inv%Mod;
}
inline void NTT(int n,int m,vector<int> &A,vector<int> B)
{
int len=n+m;
int T=1;
while(T<=len) T<<=1;
Get_Rev(T);
A.resize(T), B.resize(T);
for(ri int i=n+1;i<T;i++) A[i]=0;
for(ri int i=m+1;i<T;i++) B[i]=0;
DFT(T,A,1), DFT(T,B,1);
for(ri int i=0;i<T;i++) A[i]=1ll*A[i]*B[i]%Mod;
DFT(T,A,0);
}
void GetInv(int n,vector<int> &F,vector<int> G)
{
if(n==1) { F[0]=ksc(G[0],Mod-2); return; }
GetInv((n+1)/2,F,G);
vector<int> A,B;
int T=1;
while(T<=n+n) T<<=1;
Get_Rev(T);
A.resize(T), B.resize(T);
for(ri int i=0;i<n;i++) A[i]=F[i], B[i]=G[i];
DFT(T,A,1), DFT(T,B,1);
for(ri int i=0;i<T;i++) A[i]=(2ll*A[i]%Mod-1ll*B[i]*A[i]%Mod*A[i]%Mod+Mod)%Mod;
DFT(T,A,0);
for(ri int i=0;i<n;i++) F[i]=A[i];
}
inline void GetDao(int n,vector<int> &A,vector<int> B)
{
for(ri int i=0;i<n-1;i++) A[i]=1ll*(i+1)*B[i+1]%Mod;
A[n-1]=0;
}
inline void GetJi(int n,vector<int> &A,vector<int> B)
{
for(ri int i=1;i<n;i++) A[i]=1ll*B[i-1]*inv[i]%Mod*fac[i-1]%Mod;
A[0]=0;
}
inline void GetLn(int n,vector<int> &F,vector<int> G)
{
vector<int> A,B;
A.resize(n), B.resize(n);
GetDao(n,A,G);
GetInv(n,B,G);
NTT(n,n,A,B);
GetJi(n,F,A);
}
struct Node { int x,y; }; int I2;
inline Node operator * (Node a,Node b)
{
int w1=(1ll*a.x*b.x%Mod+1ll*a.y*b.y%Mod*I2%Mod)%Mod;
int w2=(1ll*a.x*b.y%Mod+1ll*a.y*b.x%Mod)%Mod;
return (Node){w1,w2};
}
inline Node KSC(Node x,int p) { Node res=(Node){1,0}; for(;p;p>>=1, x=x*x) if(p&1) res=res*x; return res; }
inline bool Check(int x) { return ksc(x,(Mod-1)/2)==1; }
inline int Rand()
{
int w=1ll*rand()*rand()%Mod;
w+=rand()-rand();
w=(w%Mod+Mod)%Mod;
return w;
}
inline int Cipolla(int n)
{
if(!n) return 0;
int a=0;
while(Check((1ll*a*a%Mod-n+Mod)%Mod)) a=Rand();
I2=(1ll*a*a%Mod-n+Mod)%Mod;
int X1=KSC((Node){a,1},(Mod+1)/2).x;
return min(X1,Mod-X1);
}
signed main()
{
srand(time(NULL));
r[23][1]=ksc(3,119), r[23][0]=ksc(ksc(3,Mod-2),119);
for(ri int i=22;~i;i--) r[i][0]=1ll*r[i+1][0]*r[i+1][0]%Mod, r[i][1]=1ll*r[i+1][1]*r[i+1][1]%Mod;
fac[0]=1;
for(ri int i=1;i<=N;i++) fac[i]=1ll*fac[i-1]*i%Mod;
inv[N]=ksc(fac[N],Mod-2);
for(ri int i=N;i;i--) inv[i-1]=1ll*inv[i]*i%Mod;
n=read(), n++;
vector<int> A,B;
A.resize(n), B.resize(n);
int g2=Cipolla(2);
for(ri int i=1;i<n;i++)
{
int w=1ll*inv[i]*ksc(ksc(g2,1ll*i*i%(Mod-1)),Mod-2)%Mod;
if(i&1) B[i]=Mod-w;
else B[i]=w;
}
B[0]=1;
GetInv(n,A,B);
for(ri int i=0;i<n;i++) A[i]=1ll*A[i]*ksc(g2,1ll*i*i%(Mod-1))%Mod;
GetLn(n,A,A);
for(ri int i=1;i<n;i++) printf("%d\n",1ll*A[i]*fac[i]%Mod);
puts("");
return 0;
}
© 著作权归作者所有
举报
相关热门文章
发表评论
0/200
