[关闭]
@xzyxzy 2018-08-05T21:55:54.000000Z 字数 956 阅读 1415

[UOJ266]Alice和Bob又在玩游戏

题解

作业部落

评论地址


TAG:博弈

题意

不同于树的删边游戏,删掉一个点删去的是到根的路径

题解

这题只和计算有关,博弈的有关内容可以移步这篇博客
这和翻棋子游戏不同!每个点不能单独考虑

代码

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. using namespace std;
  6. int read()
  7. {
  8. char ch=getchar();int h=0,t=1;
  9. while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
  10. if(ch=='-') t=-1,ch=getchar();
  11. while(ch>='0'&&ch<='9') h=h*10+ch-'0',ch=getchar();
  12. return h*t;
  13. }
  14. const int mod=998244353;
  15. const int N=1<<21;
  16. const int inv=499122177;
  17. int n,A[N],B[N],bit3[N],l;
  18. void FWT_xor(int *P,int op)
  19. {
  20. for(int i=1;i<l;i<<=1)
  21. for(int j=0,p=i<<1;j<l;j+=p)
  22. for(int k=0;k<i;k++)
  23. {
  24. int X=P[j+k],Y=P[j+k+i];
  25. P[j+k]=1ll*(X+Y)%mod*op%mod;
  26. P[j+k+i]=1ll*((X-Y)%mod+mod)*op%mod;
  27. }
  28. }
  29. int main()
  30. {
  31. n=read();A[0]=n;bit3[0]=1;int mx=0;
  32. for(int i=1;i<=n;i++) bit3[i]=bit3[i-1]*3ll%mod;
  33. for(int i=1,x;i<=n;i++) A[x=read()]+=2,mx=max(mx,x);
  34. for(l=1;l<=mx;l<<=1);
  35. FWT_xor(A,1);
  36. for(int i=0;i<l;i++)
  37. {
  38. int x=(3ll*n-A[i]+mod)*inv%mod*inv%mod;
  39. A[i]=bit3[n-x]; if(x&1) A[i]=mod-A[i];
  40. }
  41. FWT_xor(A,inv);
  42. printf("%d\n",(A[0]-1+mod)%mod);
  43. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注