[Codeforces 317D]Game with Powers

題目連結

如果要看懂這個題解，請先了解組合賽局的$SG$函數和$Nim$和的性質

不曉得您有沒有看出，$2$的冪次方組成的數字可以當作是獨立的子遊戲呢？

同理

$3$的冪次方組成的數字也可以當作獨立的子遊戲

但$4$的冪次方就不能了，因為$4$已經被歸類在$2$的冪次方

$5$的冪次方可以

$6$的冪次方也可以

......

好像知道了甚麼

我們只要算出這些子遊戲的$SG\ value$，然後$\oplus$起來就好了嘛XD ($\oplus$是$XOR$的符號)

可以發現，如果某個子遊戲裡面只有一個數字，那麼它的$SG\ value$就一定是$1$了

我們只要關心以$2\sim\sqrt{N}$為底的子遊戲，它的$SG\ value$怎麼算就好了

可以發現，每個子遊戲最多包含$30$個數字

而這個遊戲的底數是甚麼並不重要，我們只需關心剩下的數字分別是幾次方

因此，可以簡單地用$bitmask$+離散記憶化搜索 (我使用了$map$) 來計算

可是，這樣還不夠快

可以發現，我們要求$SG\ value$的狀態，表示成$bitmask$永遠是一堆$1$組成

因此，可以先將$2^{1}-1$、$2^{2}-1$、$2^{3}-1$、$2^{4}-1$、...、$2^{30}-1$的答案在本機先算好 (參見// for(int i=0;i<=30;i++)printf("%d %d\n",(1<<i)-1,GetSG((1<<i)-1));)，然後直接寫進程式碼就好了

要記得排除$\sqrt{N}\sim N$中已經被算進前面的子遊戲的數字

如果算出來有奇數個數字，就把答案$\oplus 1$

還有

$1$自己也是一個獨立的子遊戲，要再把答案$\oplus 1$

答案為$0$時先手敗，否則先手勝

時間複雜度：$O(\sqrt{N}\log N)$ (經過本機的預計算，$SG\ value$的取得可以當作$O(1)$了)

code:

#include<cstdio>
#include<cassert>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
map<int,int>SG;
int GetSG(const int s)
{
    {const auto it=SG.find(s);if(it!=SG.end())return it->second;}
    bool *vis=new bool[31];
    for(int i=0;i<=30;i++)vis[i]=false;
    for(int i=0;i<=30;i++)if(s&(1<<i))
    {
        int nxts=s;
        for(int j=1;(i+1)*j-1<=30;j++)nxts&=~(1<<((i+1)*j-1));
        vis[GetSG(nxts)]=true;
    }
    int &ans=SG[s]=0;
    for(;vis[ans];ans++);
    delete[]vis;
    return ans;
}
int N;
int main()
{
//    freopen("in.txt","r",stdin);
    SG[0]=0;
//    for(int i=0;i<=30;i++)printf("%d %d\n",(1<<i)-1,GetSG((1<<i)-1));
    if(true)
    {
        int *ans=new int[31]{0,1,2,1,4,3,2,1,5,6,2,1,8,7,5,9,8,7,3,4,7,4,2,1,10,9,3,6,11,12,14};
        for(int i=0;i<=30;i++)SG[(1<<i)-1]=ans[i];
    }
    while(scanf("%d",&N)==1)
    {
        int ans=0;
        set<int>all;
        for(int i=2;i<=N;i++)if(all.find(i)==all.end())
        {
            int n=1,cnt=0;
            while(n<=N/i)n*=i,cnt++,all.insert(n);
            if(cnt==1)
            {
                while(!all.empty()&&*all.begin()<=i)all.erase(all.begin());
                if(((N-i+1)-(int)all.size())&1)ans^=1;
                break;
            }
            else ans^=GetSG((1<<cnt)-1);
        }
        ans^=1;
//        printf("ans=%d\n",ans);
        puts(ans==0?"Petya":"Vasya");
//        printf("ans=%d\n",ans);
//        assert(0);
    }
    return 0;
}