BZOJ4589：Hard Nim——题解-白红宇

BZOJ4589：Hard Nim——题解

阅读量：5912 次

发布时间：2019-06-19

本文共 1680 字，大约阅读时间需要 5 分钟。

Claris和NanoApe在玩石子游戏，他们有n堆石子，规则如下：

1. Claris和NanoApe两个人轮流拿石子，Claris先拿。

2. 每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。

不同的初始局面，决定了最终的获胜者，有些局面下先拿的Claris会赢，其余的局面Claris会负。

Claris很好奇，如果这n堆石子满足每堆石子的初始数量是不超过m的质数，而且他们都会按照最优策略玩游戏，那么NanoApe能获胜的局面有多少种。

由于答案可能很大，你只需要给出答案对10^9+7取模的值。

天哪这个tinymce可以用latex我才知道……以及我还是想不到dp啊。

用到一个结论：后手获胜条件是每堆石子异或和为0。

设$f[i][j]$为前$i$堆异或和为$j$的方案数，$g[i]$表示$i$是否为质数。

于是$f[i][j]=\sum_{k=0}^mf[i-1][j\oplus k]g[k]$

然后变成卷积就是$f[i][j]=\sum_{a\oplus b=j}f[i-1][a]g[b]$

同样还是把$f[i-1][a]$递归展开发现是卷积套卷积……n次，于是FWT快速幂就好了。

#include#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;typedef long long ll;const int N=1e5+5;const int p=1e9+7;const int inv=500000004;inline int add(int x,int y){ x+=y;if(x>=p)x-=p;return x;}inline int sub(int x,int y){ x-=y;if(x<0)x+=p;return x;}void FWT(int a[],int n,int on){ for(int i=1;i
                
                 <<=1){ for(int j=0;j
                 
                  <<1)){ for(int k=0;k
                  
                   >=1; } return res;}int pri[N],g[N],a[N],b[N],tot;void Euler(int n){ g[0]=g[1]=1; for(int i=2;i<=n;i++){ if(!g[i])pri[++tot]=i; for(int j=1;j<=tot;j++){ if(i*pri[j]>n)break; g[i*pri[j]]=1; if(i%pri[j]==0)break; } } for(int i=0;i<=n;i++)g[i]^=1;}int n,m;int main(){ Euler(5e4); while(scanf("%d%d",&n,&m)!=EOF){ int len=1; while(len<=m)len<<=1; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); a[0]=1; for(int i=0;i<=m;i++)b[i]=g[i]; FWT(a,len,1);FWT(b,len,1); for(int i=0;i