题解：P15324 【MX-X24-T5】「RiOI-7」ANDORXOR

· · 题解

喵喵题啊咋没人做啊。

因为赛前被 Ri 强制透题于是被禁赛了。/ll

题意

Alice 和 Bob 可以在一个 01 序列上博弈。过程如下：Alice 先手，每次两人轮流选择两个相邻位置，变成他们的与、或、异或其中一种。若最终剩下 1 则 Alice 获胜。

现给定一个包含 \{0,1,?\} 的序列，多次询问区间 [l,r]，有多少种方案使得将 ? 替换成 0/1 后 Alice 有必胜方案？

思路 Part 1

我们先来考虑什么样的 01 序列能使 Alice 必胜。

首先发现长度为奇数的话 Alice 就爆炸了。因为最后一次操作控制权在 Bob 手上，而我们注意到 Bob 总能将任意两个数变为 0。当然序列为 \{1\} 也是合法的，这两种我们特判掉。据出题人透露，有一百个验题人没有判这个。

这进而提醒我们思考：Alice 和 Bob 两人能干嘛？我们关注序列中 1 的个数，Alice 想最大化序列中剩余的 1 个数，而 Bob 想最小化。

Bob 比较牛。每次至少能够删除一个 1，只需选一个旁边的 0 与一下即可。若有两个连续的 1 Bob 会更高兴，因为他可以使用异或一下删掉两个 1。

Alice 就比较惨。她无法用两个 0 凭空变出一个 1 来，也不会选择删去任何一个 1，每次只能删去一个 0。

让我们假定 Bob 是先手。此时的策略是比较简单的。

  1. 第一阶段，优先将所有相邻的 1 都变成 0，而 Alice 此时只能帮他擦屁股把这些 0 删掉。

  2. 第二阶段，序列中所有 1 均互不相邻。此时 Alice 和 Bob 都分别只能删一个 0/1。那就比速度！因为依旧 Bob 先手，我们发现，当且仅当此时序列形态为 \pmb{101010\cdots10101} 时 Alice 能够获胜。

现在我们思考 Alice 先手的话，她能用这至关重要的第一步干什么。不考虑第一阶段所提到的 11 带来的影响，有两种情况：

  1. Alice 删去了一个 0。这意味着原序列是在 10101 基础上增加一个 0，变为 1010\cdots100101\cdots01 的形式。

  2. Alice 删去了一个 1。你先别管她为啥会自残，10101 基础上增加一个 1，消掉 11 后依然是 1010\cdots100101\cdots01 的形式。

由于长度为偶数，我们两两分段，考虑上 11 后，能使 Alice 拥有必胜策略的序列表述为：两两分段后每段可以为 \pmb{01,10,11}，且所有 \pmb{10} 均在所有 \pmb{01} 之前。

思路 Part 2

现在我们开始计数部分。

这个区间查询很有使人线段树的欲望，但是你会发现你要推一大坨（至少我是这么认为的）。

那就退一步，思考全局怎么做。考虑 dp，记 f_{i,0/1} 为前 i 位，是否出现过 01 的方案数。我们每两位为一个单位转移，记 a 为这个 01 序列，转移方程如下：

\begin{aligned} dp_{i,0}&=(c(i,11)+c(i,10))\times dp_{i-2,0}\\ dp_{i,1}&=c(i,01)\times dp_{i-2,0}+(c(i,01)+c(i,11))\times dp_{i-2,1} \end{aligned}

其中 c(i,s) 表示 a_{i-1,i} 能否为 s，能则为 1，否则为 0。

注意到这个和矩阵乘法优化 dp 的形式是很像的，我们可以使用动态 dp。像我一样没学过的也没关系，其原理与矩阵快速幂类似，将一次转移转化为两个矩阵相乘。

利用矩阵乘法有结合律的性质，我们可以使用线段树维护这一堆矩阵的区间乘积，其中代表 (i-1\sim i) 的叶子位置存储的便是 dp_{i-2,0/1}\to dp_{i,0/1} 的转移矩阵。

一次询问 l,r，我们就将 dp_{0,0/1} 乘上这段区间的矩阵积，最后和就是 dp_{r-l+1,0}+dp_{r-l+1,1}。初始化 dp_{0,0}=1,dp_{0,1}=0。

时间复杂度 O(n\log n)。带一个 8 的常数。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
int n, m, len[2];
char a[200002];
struct Matrix {
    ll v00, v01, v10, v11;
    inline Matrix operator * (Matrix b) {
        return { // 特殊的 2 * 2 矩阵直接拆开写了
            ((ll)v00 * b.v00 + (ll)v01 * b.v10) % mod, 
            ((ll)v00 * b.v01 + (ll)v01 * b.v11) % mod, 
            ((ll)v10 * b.v00 + (ll)v11 * b.v10) % mod, 
            ((ll)v10 * b.v01 + (ll)v11 * b.v11) % mod
        };
    }
}tr[2][400002];
void build(int op, int x, int l, int r) {
    if (l == r) return l += l - op, r = l + 1, 
        tr[op][x] = {
            (a[l] != '0') * ((a[r] != '1') + (a[r] != '0')), 
            (a[l] != '1') && (a[r] != '0'), 
            0, 
            (a[r] != '0') * ((a[l] != '0') + (a[l] != '1'))
        }, void(); // 转移矩阵
    int mid = l + r >> 1, ls = x << 1, rs = x << 1 | 1;
    build(op, ls, l, mid);
    build(op, rs,mid+1,r);
    tr[op][x] = tr[op][ls] * tr[op][rs];
}
Matrix query(int op, int x, int l, int r, int ansl, int ansr) {
    if (ansl <= l && ansr >= r) return tr[op][x];
    int mid = l + r >> 1, ls = x << 1, rs = x << 1 | 1;
    if (mid >= ansr) return query(op, ls, l, mid, ansl, ansr);
    if (mid <  ansl) return query(op, rs,mid+1,r, ansl, ansr);
    return query(op, ls, l, mid, ansl, ansr) * query(op, rs,mid+1,r, ansl, ansr);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    build(0, 1, 1, len[0] = (n - 1) / 2);
    build(1, 1, 1, len[1] = n / 2);
    Matrix ans;
    for (int l, r; m --; ) {
        cin >> l >> r;
        if ((r - l) & 1) 
            ans = query(l & 1, 1, 1, len[l & 1], (l + (l & 1)) / 2, (r + (l & 1)) / 2), 
            cout << ((ll)ans.v00 + ans.v01) % mod << "\n"; // 其实这里不需要在前面乘一个 dp[0]，手算一下各位贡献即可
        else cout << (l == r && a[l] != '0') << "\n"; // 记得特判
    }
}