[Luogu 5675] GZOI2017 取石子游戏

[Luogu 5675] GZOI2017 取石子游戏

批话

winsun 又来水蓝题了，不过 Nim 和线性基都是九级。。。

原题是个暴力 DP $O(n^{2}V)$，如果是模拟赛毒瘤搬题人，这部分只给 $30\mathtt{pts}$。

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le a_i<2^{31}$，开 2 秒不卡常。

这个数据范围仍然可做，不过也许就要升紫了。

01 Trie 可以做按位贪心（2024 省选，加法定向加强），简化后的线性基也可以。

问题转化

不难发现，若石子集合为 { b 1 , b 2 , ⋯   , b m } \{b_1, b_2, \cdots, b_m\} {b1​,b2​,⋯,bm​}，其 $\mathrm{xor}$ 和为 $s$，先手从 $b_i$ 中取，先手必败，当且仅当 $s\oplus b_i\ge b_i$。

欲使后手进入必败态，显然这次取完之后剩下的数的异或和为 $0$。而排除 $b_i$ 之后集合内其它数的异或和为 $s\oplus b_i$（总的异或掉自己，异或消去律），那么本轮取完之后第 $i$ 个数应当恰好剩下 $s\oplus b_i$。而 $s\oplus b_i\ge b_i$ 时，取了至少一个，剩的竟然还比原来多，显然做不到使后手失败，先手只能认输。

钦定先手第一次取了第 $i$ 堆石子，考虑计算使先手必败的方案数。

显然问题转化为，对于下标位于 $[1,i-1]\cup [i+1,n]$ 的所有数，每个数都可以选或者不选，使得已选的若干个数的异或和大于等于 $b_i$ 的方案数。

考虑线性基

设 $V$ 为位运算可能得到的最大值，原题中 $255$。

设线性基中有 $tot$ 个位置上的数非零，那么余下的 $n-tot-1$ 个数都一定可以被线性基表出（否则它应当被插入线性基）。

考虑暴力枚举每个 $x\in [b_i,V]$，若 $x$ 能够被它的线性基表出，那么答案应当累加 $2^{n-tot-1}$。（如果加入了某个能被表出的数，那么线性基中表出它的数选与不选的状态取反即可。）

这个方法就是 David_Mercury 的题解 中的做法。它的时间复杂度是 $O(nV\log V)$ 的。

考虑按位贪心优化

按照 XOR 第 $k$ 大的方法，用高斯消元把线性基化简。

// s 是存线性基的数组。
void insert(int x) {
    for (int k = 7; ~k; --k) {
        if ((x>>k)&1) {
            if (s[k]) x ^= s[k];
            else { ++tot; s[k] = x; break; }
        }
    }
}
void simplify() {
    for (int i = 0; i < 8; ++i) {
        if (!s[i]) continue;
        for (int j = i+1; j < 8; ++j) {
            if ((s[j]>>i)&1) s[j] ^= s[i];
        }
    }
}

观察 insert 和 simplify，存在一个事实：

如果 $s_i$ 非空，那么 $\forall j\ne i$，$s_j$ 的第 $i$ 位必然为 $0$，因为更高位在高斯消元的时候被消掉了，更低位在插入的时候也被消掉了。

根据上面事实以及位运算经典按位贪心的经验，有一个单次 $O(\log V)$ 可以求出 $[x,V]$ 内能被表出的数的个数的方法。

int query(int x) {
    int res = 0, cur = 0, cnt = 0;
    for (int k = 7; ~k; --k) {
        if (s[k]) ++cnt;
        if ((x>>k)&1) {
            if (s[k]) cur ^= s[k];
            else if (!((cur>>k)&1)) return res; // GG
            // Otherwise, nothing matters.
        } else {
            if (s[k]) res += 1 << (tot - cnt);
            else if ((cur>>k)&1) return res += 1 << (tot - cnt);
            // Case 2: it's always greater than x.
            // Otherwise, nothing matters.
        }
    }
    return ++res;
}

对于第 $k$ 位：

• 如果 $x$ 的当前位为 $1$：
  • 如果线性基的当前位有值，为了保证大于等于，线性基当前位的数必须选。
  • 如果当前位没有值，且已选的异或和 $cur$ 里面，当前位是 $0$，再往下怎样都做不到 $\ge x$，死棋了，当场 return。
  • 如果当前位没有值，且已选的异或和 $cur$ 里面，当前位是 $1$，那么没有影响，还能继续。
• 如果 $x$ 的当前位是 $0$：
  • 如果线性基的当前位有值，选了就一定大于 $x$，答案加上 选了当前位，后面的位随便选或不选的方案数，然后不选当前位，进入下面的计算。
  • 如果当前位没有值，且已选的异或和 $cur$ 里面，当前位是 $0$，那么没有事情发生。
  • 如果当前位没有值，且已选的异或和 $cur$ 里面，当前位是 $1$，再往下不管怎么选都一定大于 $x$，答案加上后面的位随便选或不选的方案数，然后返回。

如果上面这个过程的途中没有 return，说明最后顺利进入了恰好等于 $x$ 的情况，答案应当加 $1$。

完整代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#define fi first
#define se second
using namespace std;
using LL = long long;
using LLL = __int128;
const int MAXN = 205;
const int mod = 1e9+7;

template <typename Tp> void read(Tp &res) {
    char ch; bool op = 0; res = 0;
    do ch = getchar(), op |= ch == '-'; while (ch < '0' || ch > '9');
    do res = (res<<3)+(res<<1)+(ch&15), ch = getchar(); while(ch >= '0' && ch <= '9');
    if (op) res = -res;
}
int n, a[MAXN];

struct Base {
    int s[8], tot;
    Base() {
        tot = 0; for (int i = 0; i < 8; ++i) s[i] = 0;
    }
    void insert(int x) {
        for (int k = 7; ~k; --k) {
            if ((x>>k)&1) {
                if (s[k]) x ^= s[k];
                else { ++tot; s[k] = x; break; }
            }
        }
    }
    void simplify() {
        for (int i = 0; i < 8; ++i) {
            if (!s[i]) continue;
            for (int j = i+1; j < 8; ++j) {
                if ((s[j]>>i)&1) s[j] ^= s[i];
            }
        }
    }
    int query(int x) {
        int res = 0, cur = 0, cnt = 0;
        for (int k = 7; ~k; --k) {
            if (s[k]) ++cnt;
            if ((x>>k)&1) {
                if (s[k]) cur ^= s[k];
                else if (!((cur>>k)&1)) return res; // GG
            } else {
                if (s[k]) res += 1 << (tot - cnt);
                else if ((cur>>k)&1) return res += 1 << (tot - cnt);
            }
        }
        return ++res;
    }
} pre[MAXN], suf[MAXN];

Base operator+(const Base& A, const Base& B) {
    Base res = A;
    for (int i = 0; i < 8; ++i) {
        if (!B.s[i]) continue;
        res.insert(B.s[i]);
    }
    return res;
}

int qpow(int x, int y) {
    int res = 1;
    for (; y; y >>= 1) {
        if (y & 1) res = 1ll * res * x % mod; 
        x = 1ll * x * x % mod;
    }
    return res;
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("lg5675.in", "r", stdin);
    freopen("lg5675.out", "w", stdout);
    #endif
    // code
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i-1];
        pre[i].insert(a[i]);
    }
    for (int i = n; i; --i) {
        suf[i] = suf[i+1];
        suf[i].insert(a[i]);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        Base cur = pre[i-1] + suf[i+1];
        cur.simplify();
        ans = (ans + 1ll * cur.query(a[i]) * qpow(2, n-1-cur.tot)) % mod;
    }
    printf("%d\n", ans);
    return 0;
}

原文地址：https://blog.csdn.net/winsunboy/article/details/143052532

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！