自动搬运

查看原文

来自洛谷，原作者为

	TonyYin AFOed.

搬运于2025-08-24 22:13:15，当前版本为作者最后更新于2021-03-09 16:13:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

2022/08/04，fix：第一堆石子应小于其他堆

Nim类石子游戏介绍

（学过的话可以跳到题目分析部分

$\rm{Description}$

给定数列 $n_1, n_2, \cdots, n_k$，表示有 $k$ 堆物品，第 $i$ 堆物品的数量为 $n_i$。

两人轮流从中取物品，规则：每次可以从一堆中拿走任意正整数个物品。先拿走最后一根的人胜利。

对于给定的数列，判断先手是否必胜，若必胜，输出第一次应该在哪堆取多少物品。

$\rm{Solution}$

必胜必败分析

先手必胜，当且仅当 $n_1\oplus n_2\oplus\cdots\oplus n_k\neq 0$。

对于其他 nim游戏 ，假设状态表示为 $(a_1, a_2, \cdots,a_n)$，那么先手必胜，当且仅当 $\operatorname{sg}(a_1)\oplus \operatorname{sg}(a_2)\oplus\cdots\oplus \operatorname{sg}(a_n)$，证明BFS。

本题中 $\operatorname{sg}(i)=i$，所以有上面的结论。

证明

设 $s=n_1\oplus n_2\oplus\cdots\oplus n_k$.

也就是证明：

1. 当 $s \neq 0$ 时，存在一种取法，使得 $s=0$.
2. 当 $s=0$ 时，无论怎么取物品，$s$ 都不等于 $0$.

命题一

因为 $s\neq 0$，根据异或的定义，存在一堆物品 $i$，满足 $n_i\oplus s<n_i$ ，那么就从第 $i$ 堆取走 $n_i-(n_i\oplus s)$，剩下 $n_i\oplus s$ 个物品。

此时，$s_{\rm{new}}=n_1\oplus n_2\cdots\oplus n_k\oplus s=s\oplus s=0$.

所以命题一成立。

命题二

反证法。若否，则 $s=0$ 时，存在一种取物品的方法使得 $s_{\rm{new}}=0$.

设取走第 $i$ 堆的若干物品，第 $i$ 堆剩余 $n_i'$ 个物品。

所以 $s_{\rm{new}}=n_1\oplus n_2\cdots\oplus n_i'\oplus\cdots\oplus n_k=0=s$.

把 $s$ 的定义式代入，得到 $n_i=n_i'$，产生矛盾。

所以命题二成立。

题目分析

显然，可以看出这个问题与Nim类游戏相关。Nim类游戏先手必胜，当且仅当每堆石子的数量的异或和不为 $0$。

所以Alice先手必败仅有两种情况：

1. 异或和为 $0$；
2. 异或和不为 $0$，但Alice选择的第一堆石子无法使异或和变成0.

第一种情况容易处理，对于第二种情况，可以发现：只有指定选的第一堆石子数量，小于其他堆的异或和时，才能够做到：删去一堆棋子，异或和也不为 $0$.

所以就可以枚举Alice先选择哪一堆，然后每次DP处理：有多少种选择方法使得异或和等于 $j$.

通过数学方法进行分析，容易得到上一段中的 $j\in[0, 256]$，于是直接二维 DP 即可。

DP状态：$f_{i, j}$ 表示，当固定一堆不选时，其余的前 $i$ 堆，异或和为 $j$ 的方案数量。

每次从上一行转移过来，具体看代码就行了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 208, MAXJ = 270, mod = 1e9 + 7; 
int n;
int a[MAXN];
int dp[MAXN][MAXJ]; //dp[i][j]表示，当固定一堆不选时，其余的前i堆，异或和为j的方案数量 
signed main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	int ans = 0; dp[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			for(int k = 0; k < 256; k++) {
				if(i == j) dp[j][k] = dp[j-1][k];
				else dp[j][k] = (dp[j - 1][k] + dp[j - 1][k ^ a[j]]) % mod;
			} 
		}
		for(int j = a[i]; j < 256; j++) {
			ans = (ans + dp[n][j]) % mod;
		}
	}
	cout << ans << endl;
	return 0;
}