Description

给定一正整数n，对n个点有标号的有向无环图(可以不连通)进行计数，输出答案mod 998244353的结果

Solution

考虑 \(O(n^2)\) DP

枚举出度为 \(0\) 的点,构成的新\(DAG\)方案数为

\(f[i]=f[i-1]*C_{n}^{1}*2^{n-1}\)

即从 \(n\) 个点中选出一个点,作为出度为 \(0\) 的点,然后剩下 \(n-1\) 个点向这个点任意连边

但是 \(f[i-1]\) 中也会有出度为 \(0\) 的点,那么就算重了,考虑容斥这个算重的东西

\(f[n]=\sum_{i=1}^{n}(-1)^{i+1}**f[i-j]*C_{i}^{j}*2^{j*(i-j)}\)

即至少有一个出度为 \(0\) 的点-至少有两个的+....

这个式子可以 分治+\(NTT\) 优化

只需要拆 \(2^{j*(i-j)}\) 这个东西就行了

\(\sqrt(2)\) 的逆元可以枚举求出来

#include
    
     using namespace std;typedef long long ll;const int N=4e5+10,G=116195171,mod=998244353;inline int qm(int x,ll k){    int sum=1;    while(k){        if(k&1)sum=1ll*sum*x%mod;        x=1ll*x*x%mod;k>>=1;    }    return sum;}inline int inv(int x){return qm(x,mod-2);}int n,m,R[N];inline void NTT(int *A){    for(int i=0;i
     
      
       >1,L;    solve(l,mid);    m=r-l+1;    for(n=1,L=0;n<=m;n<<=1)L++;    for(int i=0;i
       
        >1]>>1)|((i&1)<<(L-1)),a[i]=b[i]=0;    for(int i=l;i<=mid;i++)a[i-l]=f[i];    for(int i=1,o=1?1:-1;i
        
         >n;  priwork(n);f[0]=1;  solve(0,n);  f[n]=1ll*f[n]*Fac[n]%mod*Gac[n]%mod;  printf("%d\n",f[n]);  return 0;}