校内模拟赛 T2 取石子游戏

题目描述

简要题意：现在有 $n$ 堆石子 $a_i$，$Alice$ 和 $Bob$ 准备玩最经典的取石子游戏，但是现在 $Bob$ 可以作弊，$Bob$ 在游戏开始前，可以选择移除 $k\in [0,n-1]$ 堆石子，现在再给定一个整数 $d$，求 $Bob$ 移除 $k$ 堆后先手必败的方案数，要求 $k$ 是 $d$ 的倍数

$n\le 5\times 10^5,d\le 10, a_i\le 10^6,\sum_{i=1}^na_i\le 10^7$，空间限制 $64MB$

Solution

稍微转换一下题意能够得到我们需要求选了 $m\in [0,n-1]$ 堆，异或和为 $t$ 的方案数

首先 $d$ 的倍数等价于模 $d$ 为 $0$，所以我们不需要维护具体选了几堆，直接维护模 $d$ 为多少

另外注意到 $\sum_{i=1}^n a_i\le 10^7$，我们将 $a_i$ 排序，那么前面所有数的异或和是不会超过 $2^{hb+1}-1$ 的，$hb$ 为当前数二进制最高位的 $1$，那么我们直接做背包的复杂度就为复杂度为 $O(d\sum_{i=1}^na_i)$，注意需要特判所有数都选的情况

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#define maxn 500010
#define maxk 10
#define ll long long
using namespace std;

const int p = 1000000007;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; } 

int n, m, a[maxn], h[maxn];

int f[2][maxk][1 << 20];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; int t = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i], t ^= a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i)
        for (int o = 0; o < 20; ++o) if (a[i] >> o & 1) h[i] = 1 << o + 1; 
    f[0][0][0] = 1;
    for (int i = 1, s = 0, t = 1; i <= n; ++i, swap(s, t)) 
        for (int j = 0; j < m; ++j) 
            for (int k = 0; k < h[i]; ++k) 
                f[t][j][k] = add(f[s][j == 0 ? m - 1 : j - 1][k ^ a[i]],
                                 f[s][j][k]);
    if (n % m == 0) f[n & 1][0][t] = add(f[n & 1][0][t], p - 1);
    cout << f[n & 1][0][t] << "\n";
    return 0;
}