题目描述
给出(n)堆石子, 每次可以选择将大于某个数(f)一堆平均分成多个堆, 最后不能操作的失败。
题解
10pts
直接爆搜即可。
70pts
像我们对这类题目的常规操作那样，将一整个局面分为几个子游戏，然后异或起来求答案。
注意到我们现将一堆(m)分为(i)堆，那么会分成(lfloor frac mi
floor * i)堆大小为(lfloor frac mi
floor)的，(m - lfloor frac mi
floor * i)堆大小为(lfloor frac mi
floor+1)的，
我们直接暴力求每个状态的(SG)就好了,复杂度(O(T)值域(^2))。
100pts
观察到一种拆分的方案(j,j,j...j,j+1,j+1...j+1)，
在异或的过程中(SG(j)igoplus SG(j)=0)，(SG(j+1)igoplus SG(j+1)=0)，
那么只要考虑有奇数还是偶数个(j),(j+1)即可。
但是这样还是不够的, 我们自然而然的想到, 如果将石子堆划分为(i)堆 或者是(k)堆而且 (lfloorfrac{m}{i}
floor=lfloorfrac{m}{k}
floor)
它们的后继状态都是(SG(lfloorfrac{m}{i}
floor))
或者是 (SG(lfloorfrac{m}{i}
floor+1)),
它们对答案的贡献可能是相同的, 根据上一段的论述, 这取决于 (lfloorfrac{m}{i}
floor imes i)
和 (lfloor frac{x}{i}
floor imes i)的奇偶性。
如果我们手推一下, 就会发现如果 $$lfloorfrac{m}{i}
floor=lfloorfrac{m}{i+1}
floor=lfloorfrac{m}{i+2}
floor=cdots$$
那么(i)和(i+1)对答案的贡献是相同的, (i+1)和(i+2)堆答案的贡献相同,,相同的状态我们只需要计算一次,对于(frac{m}{i})相同的所有(i),我们只需要计算最小的(i)和(i+1)即可。
然后我们对这个进行数论分块即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 1e5 + 5;
int SG[MAX_N], vis[MAX_N], T, F;
int dfs(int x) {
if (x < F) return 0;
if (~SG[x]) return SG[x];
for (int l = 2, r; l <= x; l = r + 1) {
r = (x / (x / l));
for (int j = l; j <= min(l + 1, r); j++) {
int a = x % j, b = x / j, c = j - x % j, s = 0;
if (a & 1) s ^= dfs(b + 1);
if (c & 1) s ^= dfs(b);
vis[s] = x;
}
}
for (int i = 0;; i++) if (vis[i] != x) return SG[x] = i;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
#endif
memset(SG, -1, sizeof(SG));
T = gi(), F = gi();
while (T--) {
int n = gi(), ans = 0;
for (int i = 1; i <= n; i++) ans ^= dfs(gi());
printf("%d ", (bool)ans);
}
return 0;
}