首先，Alice 先去 \(n\) 个商店中购买物品。其中第 \(i\) 个商店售卖编号为 \(i\) 的物品，且每个物品的售价为 \(a_i\)。Alice 的总花费不能超过 \(k\)。
接着，Bob 再去另外 \(m\) 个商店中购买物品。其中第 \(i\) 个商店售卖编号为 \(n+i\) 的物品，且每个物品的售价为 \(1\)。Bob 的总花费不能超过 \(m\)。
然后，Alice 和 Bob 将他们买到的物品放在一起。然后从 Alice 开始，他们轮流进行如下操作：
- 从剩余的物品中取走若干个物品（至少一个），取走的物品必须编号相同。
最后无法操作的人输。问 Alice 最初有多少种购买方式，使得 Alice 在后续的游戏中有必胜策略。Alice 的两种购买方式不同当且仅当两种方案中 Alice 在某一个商店中购买的物品的数量不同。答案对 \(10^9+7\) 取模。
\(1\le n,a_i\le 100\)，\(0\le k\le m\le 10^{18}\)。
一看，这游戏不就是 nim 游戏嘛，有结论：
设有 \(n\) 堆石子，第 \(i\) 堆石子数量为 \(a_i\)，当且仅当 \(\bigoplus\limits_{i=1}a_i\) 不为 \(0\) 时先手必胜。
分析题目的限制，第一个限制可以写成 \(\sum a_ic_i\le k\)，第二个限制是啥。
我们假如 Alice 取出的石子为 \(c_1...c_L\)，记 \(s=\bigoplus\limits_{i=1}c_i\)，那么当 \(s\le m\) 的时候，显然 Bob 可以取遍 \([1,m]\) 中的任何数，于是就输了。
所以分析完，限制就是 \(s\ge m\)。我们要求的方案满足：
- \(s_1=\sum\limits_{i=1}^L a_ic_i\le k\)
- \(s_2=\bigoplus\limits_{i=1}^Lc_i>m\)
一看新题，又不会了。\(k\) 和 \(m\) 都特别大。我们应该想到数位 dp，它也许可以计算出方案数。考虑按位考虑 \(c_i\) 二进制上的每一位，像列竖式计算一样，这样一列上每一位都是为 \(0\) 或 \(1\) 的值。 按位枚举需要新考虑的问题，一般列入状态中转移：
- 进位
- 与上界的大小关系情况
第一个限制就变成 01 背包问题了，我们对这一位求背包就可以在 \(O(n\sum a_i)\) 的时间内计算出进位的问题。
第二个限制关心的实际上就是背包取数的数量奇偶性吧，所以背包的状态加一位表示目前取物数量的奇偶性即可。
设 \(f_{i,j,0/1,0/1}\) 表示考虑了低 \(i\) 位，最终向 \(i+1\) 位的进位为 \(j\)，\(s_1\) 低 \(i\) 位与 \(k\) 低 \(i\) 位的大小关系为 \(0/1\)，\(s_2\) 低 \(i\) 位与 \(k\) 低 \(i\) 位的大小关系为 \(0/1\) 的方案数。显然 \(i\) 一维可以滚动。
这里的枚举顺序为从低位到高位，与数位 dp 不同，有时这样的状态更加方便。
时间复杂度为 \(O(n\log V\sum a_i)\)。难题啊，对着 std 才勉强看懂的。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back
using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
/*
*/
const int N = 110, mod = 1e9 + 7;
int n;
int a[N], s;
i64 k, m;
i64 f[2][N * N][2][2], g[N * N * 2][2];
bool comp(int x, int y, int z) {
if(x > y) return 1;
if(x == y && z) return 1;
return 0; //比较数组
}
int main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> k >> m;
for(int i = 1; i <= n; i++) {
std::cin >> a[i];
s += a[i];
}
int cur = 1, lst = 0; //滚动数组
f[cur][0][0][0] = 1; //初始化
for(int b = 0; b < 60; b++) { //按位 dp
std::swap(cur, lst);
for(int kl = 0; kl < 2; kl++) { //枚举先前与 k 的大小关系
for(int ml = 0; ml < 2; ml++) { //枚举先前与 m 的大小关系
for(int i = 0; i <= s; i++) g[i][0] = f[lst][i][kl][ml], f[lst][i][kl][ml] = 0; //背包初始化，继承先前的进位贡献
int nws = s; //先前的进位上界
for(int i = 1; i <= n; i++) {
nws += a[i];
for(int j = nws; j >= 0; j--) {
for(int k = 0; k < 2; k++) { //枚举取的数量的奇偶性
if(g[j - a[i]][k ^ 1] && j - a[i] >= 0) g[j][k] = (g[j][k] + g[j - a[i]][k ^ 1]) % mod; //背包
}
}
}
for(int i = 0; i <= (s << 1); i++) { //枚举进位，注意是两倍，形如 1+1/2+1/4+1/8...<=2
for(int j = 0; j < 2; j++) { //枚举异或后这一位是 0/1
int x = comp(i & 1, ((k >> b) & 1), kl), y = comp(j, ((m >> b) & 1), ml); //判断大小
f[cur][i >> 1][x][y] = (f[cur][i >> 1][x][y] + g[i][j]) % mod; //转移，到下一位时进位/2
g[i][j] = 0; //清空
}
}
}
}
}
std::cout << f[cur][0][0][1] << "\n"; //答案，表示进位为 0，sum(ac)<=k且xorsum(c)>m的方案数
return 0;
}