[关闭]
@ysner 2018-09-19T16:34:24.000000Z 字数 2348 阅读 2221

[bzoj5093]图的价值

FFT/NTT 数论


题面

“简单无向图”是指无重边、无自环的无向图(不一定连通)。
一个带标号的图的价值定义为每个点度数的次方的和。
给定,请计算所有个点的带标号的简单无向图的价值之和。
因为答案很大,请对取模输出。

解析

毒瘤毒瘤大毒瘤。。。
细节多得想吐。。。

经过思考每个点连哪些边(和其它边随便连不连),可以发现答案为

前面可以注意一下的地方是那个指数。
在模质数意义下我们是可以把它变小的。
费马小定理:若为质数,则


一般我们用它求逆元,即
但我们也可以用它化简指数,即

后面那个式子我以前推过([CF932E]Team Work)。


然后思考怎么在的时间复杂度内求出
第二类斯特林数有个由容斥得来的公式:(通过枚举至少有几个空盒)


化化简:


这样,把右边序列倒过来,就可以啦。

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cmath>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=8e5+100,mod=998244353;
  14. ll a[N],b[N],jc[N],ans,inv[N],jc2[N],p,C[N];
  15. int l,r[N],lim=1,n,m;
  16. il ll ksm(re ll S,re ll n)
  17. {
  18. re ll T=S;S=1;
  19. while(n)
  20. {
  21. if(n&1) S=S*T%mod;
  22. T=T*T%mod;
  23. n>>=1;
  24. }
  25. return S;
  26. }
  27. il void NTT(re ll *A,re int tp)
  28. {
  29. fp(i,1,lim-1) if(i<r[i]) swap(A[i],A[r[i]]);
  30. for(re int mid=1;mid<lim;mid<<=1)
  31. {
  32. re ll gu=mid<<1,W=ksm(3,(mod-1)/gu);
  33. if(tp==-1) W=ksm(W,mod-2);
  34. for(re int j=0;j<lim;j+=gu)
  35. {
  36. re ll w=1;
  37. for(re int k=0;k<mid;++k,w=w*W%mod)
  38. {
  39. re ll x=A[j+k],y=w*A[j+mid+k]%mod;
  40. A[j+k]=(x+y)%mod;A[j+mid+k]=(x-y+mod)%mod;
  41. }
  42. }
  43. }
  44. }
  45. il ll gi()
  46. {
  47. re ll x=0,t=1;
  48. re char ch=getchar();
  49. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  50. if(ch=='-') t=-1,ch=getchar();
  51. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  52. return x*t;
  53. }
  54. int main()
  55. {
  56. p=gi()-1;m=n=gi();
  57. jc[0]=inv[0]=1;fp(i,1,n) jc[i]=jc[i-1]*i%mod,inv[i]=ksm(jc[i],mod-2);//开始没有inv[0]=1
  58. re ll inv2=ksm(2,mod-2);
  59. C[0]=1;fp(i,1,n) C[i]=C[i-1]*(p-i+1)%mod*ksm(i,mod-2)%mod;
  60. jc2[0]=ksm(2,p);fp(i,1,n) jc2[i]=jc2[i-1]*inv2%mod;
  61. fp(i,0,n)
  62. {
  63. a[i]=(i&1)?mod-inv[i]:inv[i];
  64. b[i]=ksm(i,n)*inv[i]%mod;//一开始写的是p(这里在推S,p最后才用!!!)
  65. }
  66. while(lim<=n+m) lim<<=1,++l;
  67. fp(i,1,lim-1) r[i]=(r[i>>1]>>1)|((i&1)<<l-1);
  68. NTT(a,1);NTT(b,1);
  69. fp(i,0,lim-1) a[i]=a[i]*b[i]%mod;
  70. NTT(a,-1);
  71. re ll Inv=ksm(lim,mod-2);
  72. fp(i,0,n) (ans+=a[i]*Inv%mod*jc[i]%mod*C[i]%mod*jc2[i]%mod)%=mod;
  73. (ans*=(p+1)*ksm(2,((ll)(p+1)*p/2-p)%(mod-1))%mod)%=mod;
  74. printf("%lld\n",ans);
  75. return 0;
  76. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注