2016年3月5日 星期六

[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;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原