[HNOI2014]江南乐

P3235 [HNOI2014]江南乐

题目大意

有$t$组游戏和一个数$f$，每组游戏有$n$堆石子，两个人轮流操作。

每次操作，玩家可以选定一个不小于$2$的正整数$m$，然后将任意一堆石子数量大于等于$f$的石子分成$m$堆，使这$m$堆中石子数最多的一堆至多比石子数最少的一堆多至少一堆石子。（即尽量平均分配）。当一个玩家不能操作的时候，他就输了。

两个人都采用最优策略。如果先手必胜，则输出$1$；否则输出$0$。

数据范围

$1\le t\le 100,1\le n\le 100,1\le f\le 100000$

每堆石子的数量$\le 100000$

题解

首先，我们要求在只有一堆石子的时候的$sg$值。初始值为sgi=0(1≤i<f)sg_i=0(1\\leq i<f)sgi​=0(1≤i<f)。

若当前的这堆石子有$i$个，枚举其分成$m$堆，那么石子个数为⌊im⌋\\lfloor\\dfrac im\\rfloor⌊mi​⌋的有$i-i\%m$堆石子，石子个数为⌊im⌋+1\\lfloor\\dfrac im\\rfloor+1⌊mi​⌋+1的有$i\%m$堆石子。我们只需要求它们的异或和即可。

我们可以发现，如果$i-i\%m$为偶数，我们不需要异或⌊im⌋\\lfloor\\dfrac im\\rfloor⌊mi​⌋，只有$i-i\%m$为奇数时才要异或。$i\%m$和⌊im⌋+1\\lfloor\\dfrac im\\rfloor+1⌊mi​⌋+1也同理。那么，在已知$i$和$m$的情况下，可以$O(1)$求出其异或和。

枚举$i$和$m$，求$sg$值，这样做的时间复杂度为O(f2)O(f^2)O(f2)，会TLE。

我们考虑优化。上文得出石子个数为⌊im⌋\\lfloor\\dfrac im\\rfloor⌊mi​⌋的有$i-i\%m$堆石子，石子个数为⌊im⌋+1\\lfloor\\dfrac im\\rfloor+1⌊mi​⌋+1的有$i\%m$堆石子。我们可以发现，在$m$取一段值的时候，⌊im⌋\\lfloor\\dfrac im\\rfloor⌊mi​⌋是不变的（这就是数论分块）。

在⌊im⌋\\lfloor\\dfrac im\\rfloor⌊mi​⌋相等的一段中，我们来讨论$i-i\%m$和$i\%m$的奇偶性。

一类石子：i−i%m=i−(i−m×⌊im⌋)=m×⌊im⌋i-i\\%m=i-(i-m\\times \\lfloor\\dfrac im\\rfloor)=m\\times \\lfloor\\dfrac im\\rfloori−i%m=i−(i−m×⌊mi​⌋)=m×⌊mi​⌋

二类石子：i%m=i−m×⌊im⌋i\\%m=i-m\\times \\lfloor\\dfrac im\\rfloori%m=i−m×⌊mi​⌋

当$m=m+1$时，一类石子的数量增加了⌊im⌋\\lfloor\\dfrac im\\rfloor⌊mi​⌋，二类石子的数量减少了⌊im⌋\\lfloor\\dfrac im\\rfloor⌊mi​⌋

• 如果⌊im⌋\\lfloor\\dfrac im\\rfloor⌊mi​⌋为奇数，则两类石子的数量的奇偶性都改变
• 如果⌊im⌋\\lfloor\\dfrac im\\rfloor⌊mi​⌋为偶数，则两类石子的数量的奇偶性都不变

在$m=m+2$时两类石子的奇偶性一定和原来的奇偶性相同，所以不用考虑，$m+3$的和$m+1$时也相同，以此类推。

那么对于每一个含有相同的⌊im⌋\\lfloor\\dfrac im\\rfloor⌊mi​⌋的段，我们只需要考虑$m$和$m+1$的情况。

时间复杂度为O(ff)O(f\\sqrt f)O(ff​)。

code

#include<iostream>
#include<cstdio>
using namespace std;
int t,f,n,ans,a[105],z[100005],sg[100005];
int main()
{scanf("%d%d",&t,&f);for(int i=1;i<f;i++){sg[i]=0;}for(int i=f;i<=100000;i++){for(int j=2;j<=i;j=i/(i/j)+1){for(int k=j;k<=min(i,j+1);k++){int v1=i/k,v2=i%k,now=0;if(v2&1) now^=sg[v1+1];if(k-v2&1) now^=sg[v1];z[now]=i;}}int x=0;for(;z[x]==i;x++);sg[i]=x;}while(t--){scanf("%d",&n);ans=0;for(int i=1,x;i<=n;i++){scanf("%d",&x);ans^=sg[x];}if(ans) printf("1 ");else printf("0 ");}return 0;
}