我中间有一步没开LongLong，然后快速幂的时候就GG了 大概就是：
f(n)代表n个点的无向连通图数目g(n)代表n个点的无向图数目g(n)=2n(n−1)2考虑枚举1个点所在连通块的点的个数g(n)=∑i=1nC(n−1,i−1)∗f(i)∗g(n−i)这东西是不是长得很像卷积(明明是1004535809像卷积)然后我们把组合数拆开之后：g(n)=∑i=1n(n−1)!f(i)g(n−i)(i−1)!(n−i)!两边同时除以(n−1)!g(n)(n−1)!=∑i=1nf(i)(i−1)!∗g(n−i)(n−i)!这样就变成卷积了qwq然后设这三部分分别为A,B,C那么有：A=B∗C那么B=AC那么C求个逆元，然后乘上A就好了 f ( n ) 代 表 n 个 点 的 无 向 连 通 图 数 目 g ( n ) 代 表 n 个 点 的 无 向 图 数 目 g ( n ) = 2 n ( n − 1 ) 2 考 虑 枚 举 1 个 点 所 在 连 通 块 的 点 的 个 数 g ( n ) = ∑ i = 1 n C ( n − 1 , i − 1 ) ∗ f ( i ) ∗ g ( n − i ) 这 东 西 是 不 是 长 得 很 像 卷 积 ( 明 明 是 1004535809 像 卷 积 ) 然 后 我 们 把 组 合 数 拆 开 之 后 ： g ( n ) = ∑ i = 1 n ( n − 1 ) ! f ( i ) g ( n − i ) ( i − 1 ) ! ( n − i ) ! 两 边 同 时 除 以 ( n − 1 ) ! g ( n ) ( n − 1 ) ! = ∑ i = 1 n f ( i ) ( i − 1 ) ! ∗ g ( n − i ) ( n − i ) ! 这 样 就 变 成 卷 积 了 q w q 然 后 设 这 三 部 分 分 别 为 A , B , C 那 么 有 ： A = B ∗ C 那 么 B = A C 那 么 C 求 个 逆 元 ， 然 后 乘 上 A 就 好 了 代码： #include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> #include<cstdlib> #define LL long long using namespace std; inline int read(){ int x=0,f=1;char ch=' '; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return x*f; } const int N=5e5+5,mod=1004535809,g=3,gi=334845270; inline LL ksm(LL a,LL n){ LL ans=1LL; while(n){ if(n&1)ans=ans*a%mod; a=a*a%mod; n>>=1; } return ans; } int n,R[N],m,bin[1<<23]; LL f[N],ans[N],h[N],tmp[N],inv_h[N],fac[N],inv[N],ifac[N],C[N]; inline void NTT(LL *a,int n,int f){ int L=bin[n]; for(int i=0;i<n;++i)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); for(int i=0;i<n;++i)if(i<R[i])swap(a[i],a[R[i]]); for(int i=1;i<n;i<<=1){ LL wn=ksm(f==1?g:gi,(mod-1)/(i<<1)); for(int j=0;j<n;j+=(i<<1)){ LL w=1LL; for(int k=0;k<i;++k,w=w*wn%mod){ LL x=a[j+k],y=w*a[j+k+i]%mod; a[j+k]=(x+y)%mod;a[j+k+i]=(x-y+mod)%mod; } } } if(f==-1)for(int i=0;i<n;++i)a[i]=a[i]*ksm(n,mod-2)%mod; } inline void poly_inv(LL *a,LL *b,int n){ if(n==1){b[0]=ksm(a[0],mod-2);return;} poly_inv(a,b,(n+1)>>1); int m=1; for(;m<(n<<1);m<<=1); for(int i=0;i<n;++i)tmp[i]=a[i]; for(int i=n;i<m;++i)tmp[i]=0; NTT(tmp,m,1);NTT(b,m,1); for(int i=0;i<m;++i) b[i]=(2LL*b[i]%mod-tmp[i]*b[i]%mod*b[i]%mod+mod)%mod; NTT(b,m,-1); for(int i=n;i<m;++i)b[i]=0; return; } int main(){ for(int i=0;i<22;++i)bin[1<<i]=i; n=read();fac[0]=ifac[0]=inv[0]=inv[1]=1; for(int i=1;i<=n;++i)fac[i]=fac[i-1]*i%mod; for(int i=2;i<=n;++i)inv[i]=(mod-mod/i)*inv[mod%i]%mod; for(int i=1;i<=n;++i)ifac[i]=ifac[i-1]*inv[i]%mod; for(int i=1;i<=n;++i)C[i]=(LL)i*(i-1)/2%(mod-1); for(int i=1;i<=n;++i)f[i]=ksm(2LL,C[i])*ifac[i-1]%mod; for(int i=0;i<=n;++i)h[i]=ksm(2LL,C[i])*ifac[i]%mod; for(m=1;m<=n;m<<=1); poly_inv(h,inv_h,n+1); NTT(f,m,1);NTT(inv_h,m,1); for(int i=0;i<m;++i)ans[i]=f[i]*inv_h[i]%mod; NTT(ans,m,-1); printf("%lld",ans[n]*fac[n-1]%mod); return 0; }