这题太珂怕了……如果是我的话完全想不出来……
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #define ll long long 6 #define swap(x,y) (x^=y,y^=x,x^=y) 7 #define mul(x,y) (1ll*(x)*(y)%P) 8 #define add(x,y) (x+y>=P?x+y-P:x+y) 9 #define dec(x,y) (x-y<0?x-y+P:x-y) 10 using namespace std; 11 const int N=1000005,P=1004535809; 12 inline int ksm(int a,ll b){ 13 int res=1; 14 while(b){ 15 if(b&1) res=mul(res,a); 16 a=mul(a,a),b>>=1; 17 } 18 return res; 19 } 20 int n,r[N],A[N],B[N],fac[N],finv[N],O[N],C[N],F[N],G[N]; 21 inline void init(){ 22 fac[0]=fac[1]=finv[0]=1; 23 for(int i=2;i<=n;++i) fac[i]=mul(fac[i-1],i); 24 finv[n]=ksm(fac[n],P-2); 25 for(int i=n-1;i;--i) finv[i]=mul(finv[i+1],i+1); 26 } 27 void NTT(int *A,int type,int len){ 28 int limit=1,l=0; 29 while(limit<len) limit<<=1,++l; 30 for(int i=0;i<limit;++i) 31 r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); 32 for(int i=0;i<limit;++i) 33 if(i<r[i]) swap(A[i],A[r[i]]); 34 for(int mid=1;mid<limit;mid<<=1){ 35 int R=mid<<1,Wn=ksm(3,(P-1)/R);O[0]=1; 36 for(int j=1;j<mid;++j) O[j]=mul(O[j-1],Wn); 37 for(int j=0;j<limit;j+=R){ 38 for(int k=0;k<mid;++k){ 39 int x=A[j+k],y=mul(O[k],A[j+k+mid]); 40 A[j+k]=add(x,y),A[j+k+mid]=dec(x,y); 41 } 42 } 43 } 44 if(type==-1){ 45 reverse(A+1,A+limit); 46 for(int i=0,inv=ksm(limit,P-2);i<limit;++i) 47 A[i]=mul(A[i],inv); 48 } 49 } 50 void Inv(int *a,int *b,int len){ 51 if(len==1) return (void)(b[0]=ksm(a[0],P-2)); 52 Inv(a,b,len>>1); 53 for(int i=0;i<len;++i) F[i]=a[i],G[i]=b[i]; 54 NTT(F,1,len<<1),NTT(G,1,len<<1); 55 for(int i=0;i<(len<<1);++i) 56 F[i]=mul(mul(F[i],G[i]),G[i]); 57 NTT(F,-1,len<<1); 58 for(int i=0;i<len;++i) b[i]=(1ll*(b[i]<<1)%P+P-F[i])%P; 59 } 60 int main(){ 61 // freopen("testdata.in","r",stdin); 62 scanf("%d",&n);init(); 63 int len=0;for(len=1;len<=(n*2);len<<=1); 64 A[0]=1; 65 for(int i=1;i<=n;++i) A[i]=mul(ksm(2,1ll*i*(i-1)/2),finv[i]); 66 Inv(A,B,len); 67 for(int i=1;i<=n;++i) C[i]=mul(ksm(2,1ll*i*(i-1)/2),finv[i-1]); 68 NTT(B,1,len),NTT(C,1,len); 69 for(int i=0;i<len;++i) B[i]=mul(B[i],C[i]); 70 NTT(B,-1,len); 71 printf("%d ",mul(B[n],fac[n-1])); 72 return 0; 73 }