P3235-[HNOI2014]江南樂【整除分塊,SG函數】

正題

題目連結:https://www.luogu.com.cn/problem/P3235

題目大意

\(T\)組遊戲，固定給出\(F\)。每組遊戲有\(n\)個石頭，每次操作的人可以選擇一個數量不少于\(F\)的石堆并把它盡量均攤成\(M\)堆\((M>1)\)。無法操作的人輸，求每組遊戲是否先手必勝。

解題思路

每個石頭之間互不影響，是以求出它們的\(SG\)函數然後異或起來就好了。

設\(sg_i\)表示\(i\)個石頭的\(SG\)函數，然後暴力的想法是枚舉\(M\)然後求答案，但是這樣顯然過不了。

發現對于一個\(M\)和石頭數量\(n\)，能産生\(n\%M\)個大小\(\lfloor\frac{n}{M}\rfloor+1\)的石頭堆和\(M-n\% M\)個大小\(\lfloor\frac{n}{M}\rfloor\)的石頭堆。

額，好像就可以整除分塊了。每次整除分塊出來的一個區間\([l,r]\)，如果\(l=r\)直接計算。

如果\(l\neq r\)的情況好像比較麻煩，其實隻需要考慮\(l\)和\(l+1\)就好了，因為如果再往後的奇偶性就會重複。

時間複雜度\(O(n\sqrt n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int T,F,cnt,cl[N],sg[N];
bool v[N];
void add(int x)
{if(!v[x])cl[++cnt]=x;v[x]=1;return;}
void clear(){
    while(cnt)v[cl[cnt]]=0,cnt--;
    return;
}
int main()
{
    scanf("%d%d",&T,&F);
    for(int i=F;i<N;i++){
        for(int l=2,r;l<=i;l=r+1){
            r=i/(i/l);
            int k=i%l,p=i/l,q=p+1;
            if((k&1)&&((l-k)&1))add(sg[p]^sg[q]);
            else if((k&1)&&!((l-k)&1))add(sg[q]);
            else if(!(k&1)&&((l-k)&1))add(sg[p]);
            else add(0);
            if(l!=r){
                l++;k=i%l;
                if((k&1)&&((l-k)&1))add(sg[p]^sg[q]);
                else if((k&1)&&!((l-k)&1))add(sg[q]);
                else if(!(k&1)&&((l-k)&1))add(sg[p]);
                else add(0);
            }
        }
        while(v[sg[i]])sg[i]++;
        clear();
    }
    while(T--){
        int n,ans=0;
        scanf("%d",&n);
        while(n--){
            int x;scanf("%d",&x);
            ans^=sg[x];
        }
        if(ans)printf("1 ");
        else printf("0 ");
    }
    return 0;
}