BZOJ4589 Hard Nim
zzxLLL
·
·
题解
BZOJ4589
Claris 和 NanoApe 在玩石子游戏，他们有 n 堆石子，规则如下：
- Claris 和 NanoApe 两个人轮流拿石子，Claris 先拿。
- 每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后 1 颗石子的人获胜。
不同的初始局面，决定了最终的获胜者，有些局面下先拿的 Claris 会赢，其余的局面 Claris 会负。Claris 很好奇，如果这 n 堆石子满足每堆石子的初始数量是不超过 m 的质数，而且他们都会按照最优策略玩游戏，那么 NanoApe 能获胜的局面有多少种。由于答案可能很大，你只需要给出答案对 10 ^ 9 + 7 取模的值。
---
$n$ 堆石子相互独立，所以分开考虑。对于一堆石子，$\operatorname{SG}(x)$ 表示剩下 $x$ 个石子时的 $\operatorname{SG}$ 函数值。归纳法容易证明 $\operatorname{SG}(x) = x$，即石子个数即其 $\operatorname{SG}$ 函数值。
考虑后手胜时，$\operatorname{xor}_{i = 1} ^ n \operatorname{SG}(x_i) = 0$ 即 $\operatorname{xor}_{i = 1} ^ n x_i = 0$。题意转化为在 $[1, m]$ 中选 $n$ 个质数（可以重复）使其异或和为 $0$。
考虑 dp，$f_{t, x}$ 表示选了 $t$ 个质数，异或和为 $x$ 的方案数。暴力做是 $O(nmk)$ 的，$k$ 表示其中 $[1, m]$ 中的质数个数。
考虑优化，可以处理出 $g_{k, x}$ 表示选了 $2 ^ k$ 个质数，异或和为 $x$ 的方案数。然后类似快速幂，可以快速求出 $f_{t, x}$。预处理 $g$ 的复杂度是 $m ^ 2 \log n$ 的，$g$ 贡献给 $f$ 的总复杂度也是是 $m ^ 2 \log n$ 的。
进一步地，发现 $f, g$ 的转移都是形如 $C_i = \sum\limits_{j \operatorname{xor} k = i} A_j B_k$ 的，可以用 FWT 将一个 $m$ 优化成 $\log m$。最后时间复杂度为 $m \log m \log n$。
```cpp
#pragma GCC optimize("Ofast")
#include<cstring>
#include<iostream>
const int V = 2e5;
const int mod = 1e9 + 7;
bool mark[V];
int pri[V], cnt;
void Sieve() {
mark[1] = mark[0] = true;
for (int i = 2; i < V; i++) {
if (!mark[i]) pri[++cnt] = i;
for (int j = 1; j <= cnt && i * pri[j] < V; j++) {
mark[i * pri[j]] = true;
if (i % pri[j] == 0) break;
}
}
}
int n, m, N, f[35][V], ans[V];
int hbit[V];
void FWT_XOR(int* a, int v) {
for (int k = 2; k <= (1 << N); k <<= 1)
for (int len = k >> 1, i = 0; i < (1 << N); i += k)
for (int j = i; j < i + len; j++) {
int x = a[j], y = a[j + len];
a[j] = 1ll * (x + y) * v % mod, a[j + len] = 1ll * (x - y + mod) * v % mod;
}
}
int main() {
Sieve();
hbit[0] = 0;
for (int i = 1; i < V; i++) hbit[i] = hbit[i >> 1] + 1;
while (std::cin >> n >> m) {
memset(f, 0, sizeof f);
memset(ans, 0, sizeof ans);
N = hbit[m];
for (int i = 1; i <= cnt; i++)
if (pri[i] <= m) f[0][pri[i]]++;
else break;
ans[0] = 1;
int cur = 0;
FWT_XOR(ans, 1);
FWT_XOR(f[cur], 1);
for (; n; n >>= 1) {
//FWT_XOR(f[cur], 1);
if (n & 1) {
//FWT_XOR(ans, 1);
for (int i = 0; i < (1 << N); i++) ans[i] = 1ll * ans[i] * f[cur][i] % mod;
//FWT_XOR(ans, (mod + 1) >> 1);
}
for (int i = 0; i < (1 << N); i++) f[cur + 1][i] = 1ll * f[cur][i] * f[cur][i] % mod;
//FWT_XOR(f[++cur], (mod + 1) >> 1);
cur++;
}
FWT_XOR(ans, (mod + 1) >> 1);
std::cout << ans[0] << '\n';
}
return 0;
}
```