【20省选十联测day10】Easy Win

题意

原题链接

有 \(n\) 堆石子，\(n\le 5\times 10^5\)，每堆石子有 \(a_i\) 个，\(a_i\le n\)。Alice 和 Bob 每次可以从，某一堆取至少 \(1\) 颗、至多 \(x\) 颗石子，不能取的失败。Alice 先手，问对于所有 \(1\le x\le n\)，问谁胜利。

思路

对于一堆石子，计算它的 SG 函数，因为每个状态 \(m\) 可以到达状态 \(\max(0,m-x)\sim m-1\)，所以 \(SG(m)=m\bmod (x+1)\)。对于 \(n\) 堆石子，全为 \(0\) 的必败态所有 SG 值 \(=0\)，它们异或和也是 \(0\)，对于异或和为 \(0\) 的情况，一次移动一定会使异或和非 \(0\)，对于异或和非 \(0\) 的情况，因为所有数字的值都 \(\le x\)，所以一定存在一种方案可以使异或和为 \(0\)。因此我们要求 \(\oplus SG(a_i)\)，时间是 \(O(n^2)\) 的。

对于每个 \(x\) 都重新求一遍 \(\oplus a_i \bmod (x+1)\) 十分浪费时间。设 \(y=x+1\)，求 \(\oplus a_i \bmod y\)。首先如果有两个相等的 \(a\)，因为是异或所以直接消掉。因此我们假设所有 \(a_i\) 互不相同。把它拍到值域上，\(b_j\) 表示是否存在 \(a_i=j\)。

上面那个式子要取模，十分麻烦，我们把它变成 \(\oplus a_i - y \lfloor \frac{a_i}{y} \rfloor\)，对于每个 \(y\)，把 \(j=[ly,ly+y)\) 的 \(b_j\) 分到一块，一块块求，每一块的 $ y \lfloor \frac{a_i}{y} \rfloor$ 相等，等于 \(ly\)。块数加起来是个调和级数，是 \(n\log n\)。

求 \(j=[ly,ly+y)\) 每个 \(j-ly[b_j]\) 异或起来不好求，考虑拆开二进制位来算。

现在求上面这坨东西在第 \(k\) 位的贡献，即第 \(k\) 位 \(1\) 的数量奇偶性。\(ly-ly=0\)，显然地。\((ly+2^k) -ly\) 在第 \(k\) 位 \(=1\)，\((ly+2^k+2^k)-ly\) 在第 \(k\) 位 \(=0\)，\((ly+2^k+2^k+2^k)-ly\) 在第 \(k\) 位 \(=1\)，\(\dots\)

所以 \(j\) 在长度为 \(2^k\) 的值域从 \(ly\) 开始，交替为一段 \(0\)、一段 \(1\)。我们要求的 \([ly,ly+y)\)，包含若干段完整的 \(2^k\)，以及末尾可能截了一段不完整的。

那一段不完整的值域，在第 \(k\) 为的数字一定相同，所以直接前缀和判断这一段值域 \(b_j\) 的和的奇偶性就好。前面那若干个完整的段可以预处理。\(f_{i,j}\) 表示以值域上 \(i\) 开始，每 \(2^j\) 为一段，奇数段不计，偶数段的值域算上的 \(b\) 的前缀和。有 \(f_{i,j}\gets f_{i+2^{j+1},j}+sumb_{[i+2^j,i+2^{j+1})}\)。

没啦。

总结

先算 \(SG\) 函数，脱掉博弈论外壳。然后对求余分块算。然后对于异或拆位算，算每一位 \(1\) 的个数奇偶性。然后预处理一下另类前缀和，然后算出另类区间和的奇偶性，然后求回异或和。时间复杂度 \(n\log^2 n\)。（整除分块和拆位各一个 \(\log\)）

code

居然卡我常

#include<bits/stdc++.h>
//#define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define isdigit(x) (x>='0'&&x<='9')
using namespace std;
typedef long long ll;
const int N=5e5+7;
template <typename T>
void read(T &sum) {
	sum=0;
	T fl=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) (ch=='-')&&(fl=-1);
	for(;isdigit(ch);ch=getchar()) sum=(sum<<3)+(sum<<1)+(ch-'0');
	sum=sum*fl;
}
template <typename T,typename... args>
void read(T &x,args&... a) {
	read(x);
	read(a...);
}
inline void write(bool op) {
	if(op) pf("Alice ");
	else pf("Bob ");
}
int n;
int a;
bitset<N> b;
bitset<20> f[N],ans;
int main() {
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("my.out","w",stdout);
	#endif
	read(n);
	rep(i,1,n) {
		read(a);
		b[a]=b[a]^1;
	}
	rep(i,1,n) b[i]=b[i]^b[i-1];
	rep(k,0,18) {
		per(i,n,0) {
			f[i][k]=f[min(n+1,i+(1<<(k+1)))][k]^b[min(n,i+(1<<k)-1)]^b[min(n,i+(1<<(k+1))-1)];
		}
	}
	int lg=1;
	rep(x,2,n+1) {
		if(x>=(1<<(lg+1))) lg++;
		ans.reset();
		for(int l=0;l*x<=n;l++) {
			rep(k,0,lg) {
				int p=x>>(k+1);
				ans[k]=ans[k]^f[l*x][k]^f[min(n+1,l*x+(p<<(k+1)))][k]^b[min(l*x+x-1,n)]^b[min(l*x+(p<<(k+1))+(1<<k)-1,min(l*x+x-1,n))];
			}
		}
		bool fl=0;
		rep(i,0,18) {
			if(ans[i]) fl=1;
		}
		write(fl);
	}
}