GDOI 2021 普及组 Day2 T2 序列 题解

你管这叫普及？

设 \(f(n,i,j)\) 为值取 \(0\sim n\)，最小的两个数最高的不相同的位是 \(i\)，最大的两个数最高的不相同的位是 \(j\) 的方案数。

主要转移是考虑最大的 \(w:2^w<n\) 将其分为 \(f(2^w-1,i,k)\times f(n-2^w,l,j)\) 容易证明 \(k\neq l\) 时这样不可能异或出 \(0\)，考虑 \(k=l\) 时，可以证明对于一个状态，前两个数/后两个数的取值是等概率的，故这四个数异或为 \(0\) 的概率是 \(\frac{1}{2^l}\) 将其减掉即可。

考虑一些特殊情况：只有两个数一个最高位 \(0\) 另一个 \(1\)；最高位第一个是 \(0\) 后面全是 \(1\)；最高位最后一个是 \(1\) 前面全是 \(0\)；最高位全是 \(0\)；最高位全是 \(1\)，简单讨论即可。

考虑可能没有逆元，一种简单的方式是 \(g(n,i,j)=\frac{f(n,i,j)}{2^j}\)，于是减掉的就是 \(g(2^w-1,i,j)\)。\(g\) 的转移和 \(f\) 类似，注意到所有有用的 \(g\) 的状态 \(n\) 都是 \(2^w-1\) 的形式，观察转移发现现在除以 \(2\) 的幂时都在对一个更大的幂除上小的幂，可以直接做。

时间复杂度 \(\operatorname{O}(\log^4n)\)。

参考实现：

#include <bits/stdc++.h>

typedef long long ll;

const int N = 125;

int lg2(ll n) { return 63 - __builtin_clzll(n); }
int f(ll n, int l, int r, int now);
int g(ll n, int l, int r, int now);
void inc(int &a, int b);
void dec(int &a, int b);

int _f[N][60][60], _g[N][60][60];
std::map<ll, int> mp;
int tot;
int pw2[120];
ll n;
int Mod;

int main() {
  scanf("%lld %d", &n, &Mod);
  pw2[0] = 1;
  for (int i = 1; i < 120; ++i)
    pw2[i] = (pw2[i - 1] << 1) % Mod;
  for (int i = 1; i <= 120; ++i) {
    for (int j = 0; j < 60; ++j) {
      for (int k = 0; k < 60; ++k) {
        _f[i][j][k] = _g[i][j][k] = -1;
      }
    }
  }
  mp[n] = tot = 1;
  int ans = (n + 1) % Mod;
  for (int i = 0; i < 60; ++i) {
    for (int j = 0; j < 60; ++j) {
      ans = (ans + f(n, i, j, 1)) % Mod;
    }
  }
  printf("%d\n", ans);
  return 0;
}

void inc(int &a, int b) { (a += b) >= Mod ? a -= Mod : a; }
void dec(int &a, int b) { (a -= b) < 0 ? a += Mod : a; }

int f(ll n, int l, int r, int now) {
  if (n == 0) return 0;
  if ((1ll << std::max(l, r)) > n) return 0;
  if (_f[now][l][r] != -1) return _f[now][l][r];
  int w = lg2(n);
  ll L = (1ll << w) - 1, R = n - (1ll << w);
  if (!mp.count(L)) mp[L] = ++tot;
  if (!mp.count(R)) mp[R] = ++tot;
  int nL = mp[L], nR = mp[R];
  int ans = (f(L, l, r, nL) + f(R, l, r, nR)) % Mod;
  if (l == w && r == w) inc(ans, 1ll * pw2[w] * ((R + 1) % Mod) % Mod);
  if (l == w) {
    for (int d = 0; d < w; ++d)
      inc(ans, 1ll * pw2[w] * f(R, d, r, nR) % Mod);
  }
  if (r == w) {
    for (int d = 0; d < w; ++d)
      inc(ans, 1ll * f(L, l, d, nL) * ((R + 1) % Mod) % Mod);
  }
  int s1 = 0;
  for (int d1 = 0; d1 < w; ++d1)
    inc(s1, f(L, l, d1, nL));
  int s2 = 0;
  for (int d2 = 0; d2 < w; ++d2)
    inc(s2, f(R, d2, r, nR));
  inc(ans, 1ll * s1 * s2 % Mod);
  for (int d = 0; d < w; ++d) {
    dec(ans, 1ll * f(L, l, d, nL) * f(R, d, r, nR) % Mod);
    inc(ans, 1ll * g(L, l, d, nL) * f(R, d, r, nR) % Mod * (pw2[d] - 1) % Mod);
  }
  return _f[now][l][r] = ans;
}
int g(ll n, int l, int r, int now) {
  if (n == 0) return 0;
  if ((1ll << std::max(l, r)) > n) return 0;
  if (_g[now][l][r] != -1) return _g[now][l][r];
  int w = lg2(n);
  ll L = (1ll << w) - 1, R = n - (1ll << w);
  if (!mp.count(L)) mp[L] = ++tot;
  if (!mp.count(R)) mp[R] = ++tot;
  int nL = mp[L], nR = mp[R];
  int ans = (g(L, l, r, nL) + g(R, l, r, nR)) % Mod;
  if (l == w && r == w) inc(ans, pw2[w]);
  if (l == w) {
    for (int d = 0; d < w; ++d)
      inc(ans, 1ll * pw2[w] * g(R, d, r, nR) % Mod);
  }
  if (r == w) {
    for (int d = 0; d < w; ++d)
      inc(ans, 1ll * f(L, l, d, nL) * (((R + 1) >> w) % Mod) % Mod);
  }
  int s1 = 0;
  for (int d1 = 0; d1 < w; ++d1)
    inc(s1, f(L, l, d1, nL));
  int s2 = 0;
  for (int d2 = 0; d2 < w; ++d2)
    inc(s2, g(R, d2, r, nR));
  inc(ans, 1ll * s1 * s2 % Mod);
  for (int d = 0; d < w; ++d) {
    dec(ans, 1ll * f(L, l, d, nL) * g(R, d, r, nR) % Mod);
    inc(ans, 1ll * g(L, l, d, nL) * g(R, d, r, nR) % Mod * (pw2[d] - 1) % Mod);
  }
  return _g[now][l][r] = ans;
}