[ARC133D] Range XOR 题解

· · 题解

牛逼逼题。

我们先考虑没有 l\le r 的限制的情况，先做个前缀和，即 s_i=\displaystyle\oplus_{i=0}^ni，那么要统计的东西就变成了：

\sum_{l=L-1}^{R-1}\sum_{r=L}^R[s_l\oplus s_r=v]

但我们会发现这玩意没有对称性，很蛋疼，于是考虑强行把区间拉平得到

\sum_{l=L-1}^{R}\sum_{r=L-1}^R[s_l\oplus s_r=v]

考虑这玩意多算了哪些东西，可以发现，我们多算的部分是 l=r 的部分（对应到一开始的式子不是合法情况），去掉这一部分后，我们会发现我们会同时统计 (l,r) 与 (r,l)，因此再除以 2 就得到了我们要的东西。

考虑做个前缀和，设

S(n,m)=\sum_{l=0}^n\sum_{r=0}^m[s_l\oplus s_r=v]

那么我们要求的东西就变成了 S(R,R)-2S(L-2,R)+S(L-2,L-2)，考虑如何求 S(n,m) 即可。

考虑 s_i 的计算，可以发现如下事实：

s[------00] =        0^------00 = ------00
s[------01] = ------00^------01 = 1
s[------10] =        1^------10 = ------11
s[------11] = ------11^------11 = 0

因此，我们有：

s_i=\begin{cases} i & i\equiv0\pmod 4\\ 1 & i\equiv1\pmod 4\\ i+1 & i\equiv2\pmod 4\\ 0 & i\equiv3\pmod 4 \end{cases}

可以发现，对于 l\equiv 1,3\pmod 4 或 r\equiv 1,3\pmod 4 的情况，由于 s_{l/r} 为常量，故可以直接计算。

可以发现当确定末两位后可以直接删掉后两位，那么就没有模 4 的限制了。

对于剩下的内容，等价于求

\sum_{l=0}^{\lfloor n/4\rfloor}\sum_{r=0}^{\lfloor m/4\rfloor}[l\oplus r=\lfloor v/4\rfloor]

而这是一个 trivial 的数位 dp，硬冲就完了。

时间复杂度 O(\log n)

#include <iostream>

using namespace std;
using LL = long long;

const int kL = 60, kB[4] = {0, 1, 3, 0};
const LL kM = 998244353;

LL L, R, v, f[kL][2][2];

LL _S(int i, LL n, bool ln, LL m, bool lm, LL v) {
  if (i == -1) {
    return 1;
  }
  LL &fs = f[i][ln][lm];
  if (~fs) {
    return fs;
  }
  fs = 0;
  for (int kn = 0, vn = (ln ? (n >> i & 1) : 1); kn <= vn; ++kn) {
    for (int km = 0, vm = (lm ? (m >> i & 1) : 1); km <= vm; ++km) {
      if ((kn ^ km) == (v >> i & 1)) {
        fs = (fs + _S(i - 1, n, ln && kn == vn, m, lm && km == vm, v)) % kM;
      }
    }
  }
  return fs;
}
LL bS(LL n, LL m, LL v) {
  for (int i = 0; i < kL; ++i) {
    for (int j = 0; j <= 1; ++j) {
      for (int k = 0; k <= 1; ++k) {
        f[i][j][k] = -1;
      }
    }
  }
  return _S(kL - 1, n, 1, m, 1, v);
}
LL S1(LL n, LL m) {
  if (n < 0 || m < 0) {
    return 0;
  }
  LL s = 0;
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      LL w = (v ^ kB[i] ^ kB[j]);
      if (w & 3) {
        continue;
      }
      w >>= 2;
      LL ci = (n >> 2) - ((n & 3) < i);
      LL cj = (m >> 2) - ((m & 3) < j);
      s = (s + bS((i & 1) ? 0 : ci, (j & 1) ? 0 : cj, w) * ((i & 1) ? (ci + 1) % kM : 1) % kM * ((j & 1) ? (cj + 1) % kM : 1) % kM) % kM;
    }
  }
  return s;
}
LL S2(LL l, LL r) { return (S1(r, r) - 2 * S1(l - 1, r) + S1(l - 1, l - 1) + 2 * kM) % kM; }

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> L >> R >> v;
  cout << (S2(L - 1, R) - (v == 0) * (R - L + 2) % kM + kM) * (kM + 1) / 2 % kM;
  return 0;
}