Game with Powers

题意：

有1~n，n个数字，两个人轮流操作，每一次一个人可以拿一个数字$x$，之后$x, x^2, x^3....x^t$全都被删掉。

给定n，问最优策略下谁赢。

解法：

考虑SG函数，可以注意到题目中取走$x$后，$x^2,x^3...$不可以取，类似石子合并问题。

对于1~n的数字可以分为两类：

　　1.不存在$x^t, t>1$，可以视为一堆只有一块石头的石子堆，$SG(1) = 0$。

　　2.存在$x^t, t>1$。

对于第一种情况，直接记录有多少个x满足条件即可，分奇偶讨论。

对于第二种情况，显然有$t<=30$，可以注意到最终$SG$值和$x$无关，这样打表预处理$sg(t)$表示$x^1,x^2...x^t$

对应的$SG$值，打表直接用$O(2^30)$状压即可（注意到$sg(t)<=30$，所以用char类型的sg数组即可节省空间）。

实际上有效的状态并不多，所以只要几秒钟（意外的快）。

最后求NIM和即可。

总效率$O(\sqrt{n}*logn)$

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define N 1000010

 #define LL long long

 using namespace std;

 bool flag[N];

 int n;

 int SG[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

 int main()

 {

     scanf("%d",&n);

     int sum=n;

     int ans=;

     for(LL i=;i*i<=n;i++)

     {

         if(flag[i]) continue;

         int tmp=;

         for(LL x=i;x<=n;x*=i)

         {

             if(x*x<=n) flag[x]=;

             tmp++;

         }

         ans^=SG[tmp];

         sum-=tmp;

     }

     ans ^= sum&;

     if(ans==) puts("Petya");

     else puts("Vasya");

     return ;

 }

巴特西

Game with Powers

最新文章

热门文章