跳转至

Zeros and Ones

原题链接

题意

\(S\) 为一个Thue-Morse sequence，构造如下：

  • 初始时，\(S=0\)
  • 每一步让 \(S=S+\overline{S}\)，其中 \(+\) 表示两个字符串拼接，\(\overline{S}\) 表示 \(S\) 按位取反得到的字符串。
Iteration S before iteration S before iteration with flipped bits Concatenated S
1 0 1 01
2 01 10 0110
3 0110 1001 01101001
4 01101001 10010110 0110100110010110
… … … …

给你两个数 \(n,m(1\le n,m\le 10^{18})\)，请问子串 \(S[0,m-1]\) 与 \(S[n,n+m-1]\) 有多少个位置不同。

⭐rating: 2500

分析

知识点：记忆化搜索+二进制

结论：定义函数 \(parity(i)\) 表示 \(i\) 二进制位中 \(1\) 的个数的奇偶性（奇数返回 \(1\)，偶数返回 \(0\)），那么 \(S_i=parity(i)\)。

注：下文所说的奇偶性为二进制中 \(1\) 的 数量 的奇偶。

证明：

  • 由于 \(S\) 的生成方式是末尾拼接其取反得到的字符串 \(S'\)，所以第 \(k(k\ge 1)\) 次扩展得到的串 \(S\) 的所有字符编号范围一定为 \([0,2^k-1]\)。
  • 对于第 \(k+1\) 次生成的 \(S'\) 中每一位的新编号 \(i'\)，满足 \(i'=i+2^k\)，由于编号 \(i\) 二进制的第 \(k\) 位之前一定为 \(0\)，因此这次的变换实际上是将 \(i\) 的第 \(k\) 位二进制转换成 \(1\) 得到 \(i'\)。
  • 显然，所有的数字都是从编号 \(0\) 变换得来的，而每次变换都会将编号的某一个二进制位从 \(0\) 变为 \(1\)，因此记录编号二进制中 \(1\) 的个数的数量即可知道该编号的数变换了几次。
  • \(S_0=0\)，由于编号 \(i\) 中有偶数个 \(1\) 就表明该数变换了偶数次，仍然是 \(0\)。因此 \(S_i=parity(i)\)。

证毕。

记录答案为 \(f(n,m)=\sum_{i=0}^{m-1}[parity(i)\neq parity(n+i)]\)。

  • 当 \(m=0\) 时，显然有 \(f(n,0)=0\) ；

  • 当 \(m\) 为偶数时，分 \(n\) 为奇偶两种情况来看。

    1. 当 \(n\) 为偶数时，如果 \(parity(2k)\neq parity(n+2k)\) 成立。

      • 由于\(2k\) 与 \(n+2k\) 都为偶数且奇偶性不同，其二进制的最末位也一定是 \(0\)，因此 \(parity(2k+1)\neq parity(n+2k+1)\) 也一定成立（同时加上 \(1\)，奇偶性都改变）。即 \(parity(2k)\neq parity(n+2k)\iff parity(2k+1)\neq parity(n+2k+1)\ [1]\)
      • 由于两个数的二进制末尾都是 \(0\)，因此删去这个 \(0\)，奇偶性也不会改变。因此 \(parity(k)\neq parity(\dfrac{n}{2}+k)\) 成立。即 \(parity(2k)\neq parity(n+2k)\iff parity(k)\neq parity(\dfrac{n}{2}+k)\ [2]\)

      因此得到这样的公式：

      \[ \begin{aligned} f(n,m) & = \sum_{i=0}^{m-1}[parity(i)\neq parity(n+i)] \\ & = 2\times\sum_{k=0}^{\frac{m}{2}-1}[parity(2k)\neq parity(n+2k)]\ [1] \\ & = 2\times\sum_{k=0}^{\frac{m}{2}-1}[parity(k)\neq parity(\dfrac{n}{2}+k)]\ [2] \\ & = 2\times f(\dfrac{n}{2},\dfrac{m}{2}) \end{aligned} \]

    2. 当 \(n\) 为奇数时：

      • 如果 \(parity(2k)\neq parity(n+2k)\) 成立。由于 \(2k\) 是偶数，\(n+2k\) 是奇数且他们的奇偶性不同，此时 \(n+2k\) 减去 \(1\)，奇偶性改变。有
      \[ \begin{aligned} parity(2k)\neq parity(n+2k) \\ \iff parity(2k)=parity(n+2k-1) \\ \iff parity(k)=parity(\dfrac{n-1}{2}+k) \\ \end{aligned} \]
      • 如果 \(parity(2k+1)\neq parity(n+2k+1)\) 成立。由于 \(2k+1\) 是奇数，\(n+2k+1\) 是偶数且他们的奇偶性不同，此时 \(2k+1\) 减去 \(1\)，奇偶性改变。有
      \[ \begin{aligned} parity(2k+1)\neq parity(n+2k+1) \\ \iff parity(2k)=parity(n+2k+1) \\ \iff parity(k)=parity(\dfrac{n+1}{2}+k) \\ \end{aligned} \]

      注意

      \(n+2k\) 和 \(2k+1\) 不能加上 \(1\)，因为加 \(1\) 后，会向第二位进位，影响奇偶性的改变。

      因此得到这样的公式：

      \[ \begin{aligned} f(n,m) & = \sum_{i=0}^{m-1}[parity(i)\neq parity(n+i)] \\ & = \sum_{k=0}^{\frac{m}{2}-1}([parity(2k)\neq parity(n+2k)]+[parity(2k+1)\neq parity(n+2k+1)]) \\ & = \sum_{k=0}^{\frac{m}{2}-1}([parity(k)=parity(\frac{n-1}{2}+k)]+[parity(k)=parity(\frac{n+1}{2}+k)]) \\ & = m-f(\frac{n+1}{2},\frac{m}{2})-f(\frac{n-1}{2},\frac{m}{2}) \end{aligned} \]

  • 当 \(m\) 为奇数的时候，可以单独判断末尾再对 \(m-1\) 进行讨论。即 \(f(n,m)=f(n,m-1)+[parity(m-1)\neq parity(n+m-1)]\)。

至此，就可以使用记忆化搜索进行求解啦。

时间复杂度为 \(O(\log n\log m)\)

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

map<pair<i64, i64>, i64> dp;

bool check(i64 a, i64 b) {
    return __builtin_parityll(a) != __builtin_parityll(b);
}

i64 f(i64 n, i64 m) {
    if (m == 0) return 0;
    if (dp.count({n, m})) return dp[ {n, m}];
    if (m & 1) return dp[ {n, m}] = f(n, m - 1) + check(m - 1, n + m - 1);
    if (n & 1) return dp[ {n, m}] = m - f((n + 1) / 2, m / 2) - f((n - 1) / 2, m / 2);
    else return dp[ {n, m}] = 2ll * f(n / 2, m / 2);
}

void solve() {
    i64 n, m;
    cin >> n >> m;
    cout << f(n, m) << endl;
}

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

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}
回到页面顶部