[Codeforces 603C]Lieges of Legendre

題目連結

題目敘述

給你N堆石頭 (原題中的cow) 和數字$K$，我們來玩一個遊戲
操作1：拿掉任一堆的任一顆石頭
操作2：選個$2n$顆石頭的石頭堆，換成$K$個各有$n$顆石頭的石頭堆
不能動就輸了，請問先手勝還是後手勝？

題解

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

可以發現，每堆牛都可以視作獨立的遊戲 (想一想，為甚麼XD)
又可以發現，當$K$是偶數時，可以視作$K=0$，當$K$是奇數時，可以視作$K=1$
因為在算$Nim$和 ($XOR$) 的時候會兩兩對消

我們當然可以使用$O(a_{i})$的記憶化搜索算出每個$a_{i}$的$SG$函數值
也就是code中被註解掉的//int GetSG(const int n)
注意到
因為操作最多兩種，因此$SG$函數值只會在$[0,2]$的範圍內

再來怎麼加速呢？
找規律吧

會發現
當$K\mod 2=0$，$SG(i)=\{0,1,2,0,1,0,1,...\}$，後面皆是$01$循環
當$K\mod 2=1$，$SG(i)=\{0,1,0,1,2,0,2,0,1,...\}$，後面奇數項均為$0$，偶數項均為$1$或$2$

要判斷$K\mod 2=1$時$SG(x)$ ($x\mod 2=0$) 是$1$還是$2$，只要算算看$SG(\frac{x}{2})$是不是$1$即可
這樣複雜度為$O(\log x)$

時間複雜度：$O(\sum_{i=1}^{N}\log a_{i})$

看不懂？可參考Coding Beans的題解

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
int N,K;
//int GetSG(const int n)
//{
//    if(n==0)return 0;
//    vector<int>sg;
//    sg.push_back(GetSG(n-1));
//    if(n%2==0)sg.push_back(K%2?GetSG(n/2):0);
//    sort(sg.begin(),sg.end());
//    int ans=0;
//    for(int i=0;i<(int)sg.size()&&sg[i]==ans;i++)ans++;
//    return ans;
//}
int GetSG(const int n)
{
    if(n==0)return 0;
    if(K%2==0)
    {
        if(n==1)return 1;
        if(n==2)return 2;
        if(n==3)return 0;
        if(n==4)return 1;
        if(n==5)return 0;
        if(n==6)return 1;
        return n&1?0:1;
    }
    else
    {
        if(n==1)return 1;
        if(n==2)return 0;
        if(n==3)return 1;
        if(n==4)return 2;
        if(n==5)return 0;
        if(n==6)return 2;
        if(n==7)return 0;
        if(n==8)return 1;
        if(n%2)return 0;
        else return GetSG(n/2)==1?2:1;
    }
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&K)==2)
    {
//        for(int i=0;i<100;i++)printf("%d ",GetSG(i));printf("%d\n",GetSG(100));
        int ans=0;
        for(int i=0,v;i<N;i++)scanf("%d",&v),ans^=GetSG(v);
        printf("%s\n",ans==0?"Nicky":"Kevin");
    }
    return 0;
}