bzoj4589 FWT xor版本

4589: Hard Nim

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 865 Solved: 484
[Submit][Status][Discuss]

Description

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

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

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

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

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

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

Input

输入文件包含多组数据，以EOF为结尾。

对于每组数据：

共一行两个正整数n和m。

每组数据有1<=n<=10^9, 2<=m<=50000。

不超过80组数据。

Output

Sample Input

3 7
4 13

Sample Output

6
120

HINT

Source

Topcoder SRM 518 Div1 Hard Nim By Tangjz

这题是一个NIM游戏，根据结论，先手输的情况只有所有的石子数xor起来的数为0

https://blog.****.net/jr_mz/article/details/51606673

这个blog比我自己瞎比比好多了。

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #define N 50007

 #define ll long long

 #define P 1000000007

 #define inv 500000004

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,len,num;

 ll A[(<<)+],B[(<<)+];

 int pri[N],np[N];

 void FWT(ll *a,int flag)

 {

     ll x,y;

     for (int h=;h<len;h<<=)

         for(int j=;j<len;j+=(h<<))

             for(int k=j;k<j+h;k++)

             {

                 if (flag==) x=a[k],y=a[k+h],a[k]=(x+y)%P,a[k+h]=(x-y+P)%P;

                 else x=a[k],y=a[k+h],a[k]=(x+y)*inv%P,a[k+h]=((x-y)*inv%P+P)%P;

             }

 }

 void pow(ll *a,ll y)

 {

     ll *b=B;b[]=;

     FWT(a,),FWT(b,);

     while(y)

     {

         if(y&) for(int i=;i<len;i++) b[i]=a[i]*b[i]%P;

         for(int i=;i<len;i++)

             a[i]=a[i]*a[i]%P;

         y>>=;

     }

     FWT(b,-);

 }

 int main()

 {

     for(int i=;i<=;i++)

     {

         if(!np[i])  pri[++num]=i;

         for(int j=;j<=num&&i*pri[j]<=;j++)

         {

             np[i*pri[j]]=;

             if(i%pri[j]==) break;

         }

     }

     while(~scanf("%d%d",&n,&m))

     {

         for(len=;len<=m;len<<=);

         memset(A,,sizeof(A));

         memset(B,,sizeof(B));

         for(int i=;i<=num&&pri[i]<=m;i++)

             A[pri[i]]=;

         pow(A,n);

         printf("%lld\n",B[]);

     }

 }

秒客网