题目简意
求强连通竞赛图的个数和从中哈密顿回路的个数。
solution
很容易求出强连通竞赛图中哈密顿回路的个数。
因为点标号不同的也算一条，所以一共有\((n-1)!\)条哈密顿回路。
你想啊，你就单拎出一条哈密顿回路，从中有\(n\)条边，剩下的边随便连，就有\(2^{C_n^2-n}\)中情况。
根据乘法原理，那么哈密顿回路的个数就是\((n-1)! \times 2^{C_n^2-n}\)。
然后是强连通竞赛图的个数。
令\(f_i\)表示\(i\)个点组成强连通竞赛图的个数。
你会发现正着直接统计比较难做，所以你考虑反着做。
\(f_i=竞赛图数-非强连通竞赛图数\)
非强连通竞赛图，缩完点后一定不是一个点。枚举\(1\)所在的强连通分量的大小\(j\)，所以动态转移方程是
\(f_i=2^{C_i^2} - \sum_j^{i-1} f_j \times C_i^j \times 2^{C_{i-j}^2}\)
中间的 \(C_i^j\) 是不是看起来很难看，所以我们把它展开 \(C_i^j= \frac{jc_i}{jc_j \times jc_{i-j}}\)，\(jc_i=i!\)。
\(f_i=2^{C_i^2} - \sum_j^{i-1} f_j \times \frac{jc_i}{jc_j \times jc_{i-j}} \times 2^{C_{i-j}^2}\)
\(f_i=2^{C_i^2} - jc_i \times \sum_j^{i-1} f_j \times \frac{1}{jc_j \times jc_{i-j}} \times 2^{C_{i-j}^2}\)
\(f_i=2^{C_i^2} - jc_i \times \sum_j^{i-1} \frac{f_j}{jc_j} \times \frac{2^{C_{i-j}^2}}{jc_{i-j}}\)
就直接套分治\(ntt\)就解决了。
Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353,G=3;
int n,rev[300005],jc[100005],f[100005],inv[100005];
int a[300005],b[300005];
int ksm(int a,int b)
{int re=1;while(b){if(b&1)re=re*a%mod;a=a*a%mod;b>>=1;}return re;
}
void ntt(int limit,int *a,int op)
{for(int i=0;i<limit;i++)if(rev[i]>i)swap(a[i],a[rev[i]]);for(int len=2;len<=limit;len<<=1){int wn=ksm(G,(mod-1)/len);if(op==-1)wn=ksm(wn,mod-2);for(int l=0;l+len-1<=limit;l+=len){int w0=1;for(int i=0;i<(len>>1);i++,w0=w0*wn%mod){int a0=a[i+l],a1=a[i+l+(len>>1)]*w0%mod;a[i+l]=(a0+a1)%mod;a[i+l+(len>>1)]=(a0+mod-a1)%mod;}}}
}
void cdq(int l,int r)
{if(l==r)return;int mid=l+r>>1,limit=1,cnt=0;cdq(l,mid);while(limit<=r-l)limit<<=1,cnt++;for(int i=0;i<limit;i++){rev[i]=(rev[i>>1]>>1)|((i&1)<<(cnt-1));a[i]=b[i]=0;}for(int i=l;i<=mid;i++)a[i-l]=f[i]*inv[i]%mod;for(int i=0;i<=r-l;i++)b[i]=ksm(2,(i-1)*i/2)*inv[i]%mod;ntt(limit,a,1),ntt(limit,b,1);for(int i=0;i<limit;i++)a[i]=a[i]*b[i]%mod;ntt(limit,a,-1);int h=ksm(limit,mod-2);for(int i=mid+1;i<=r;i++)f[i]=(f[i]+mod-a[i-l]*h%mod*jc[i]%mod)%mod;cdq(mid+1,r);
}
signed main()
{scanf("%lld",&n),jc[0]=inv[0]=1;for(int i=1;i<=n;i++){jc[i]=jc[i-1]*i%mod;f[i]=ksm(2,(i-1)*i/2);inv[i]=ksm(jc[i],mod-2);}cdq(1,n);for(int i=1;i<=n;i++){if(i==1)printf("1\n");else if(i==2)printf("-1\n");else {int tot=jc[i-1]*ksm(2,(i-1)*i/2-i)%mod;printf("%lld\n",tot*ksm(f[i],mod-2)%mod);}}return 0;
}