CF1734F (分治，记搜)

· · 题解

很奇怪的一种做法，但是过了。好像跟 editorial 的递归做法差不多。

题意

定义 S 是 Thue-Morse sequence，构造：

  1. 一开始 S=\texttt{0}
  2. 然后把 S 按位取反之后拼接在 S 后面
  3. 把 2 重复无限多次

然后 q 次询问，给定 n,m，求 S_{[0,m)} 和 S_{[n,n+m)} 有多少个位不同，下标从 0 开始。

做法

首先注意到 S_i 就是 i 的二进制中 1 的个数的奇偶性。

证明：对 i 归纳。设 i 的二进制中最高的一位是 2^k，那么 2^k\le n<2^{k+1}，由构造有 S_i 与 S_{i-2^k} 相反。\square

那么问题就变成了对多少个 0\le i<m 有 S_i\ne S_{i+n}. 分类讨论 i 的奇偶性。

若 2|i 那么设 i=2k，就有 S_i=S_k,S_{i+n}=S_{k+\lfloor n/2\rfloor}\oplus (n\bmod 2)（\oplus 记异或）。那么条件就变为 S_k\ne S_{k+\lfloor n/2\rfloor}\oplus(n\bmod 2). 然后问题就被转化为了 \dfrac{m}{2} 规模的问题。2\nmid i 的情况同理。

时间/空间复杂度

根据上面的讨论我们知道每次 (n,m)\mapsto(\lfloor n/2\rfloor,\lfloor (m+1)/2\rfloor),(\lfloor(n+1)/2\rfloor,\lfloor m\rfloor)，从而我们只需要数 m 和 n 分别可能变成哪些数。

引理：有正整数 n，每次可以把她变成 \lfloor n/2\rfloor 或者 \lfloor (n+1)/2\rfloor，至多可以达到 O(\log n) 个数。

这里感谢 I_am_Accepted 大佬的证明。

证明：不难对 k 归纳证明，操作 k 次可以达到的数是两个相邻的数。而操作次数至多 O(\log n)，即证。

从而每次至多达到 O(\log n\log m) 个不同的 (n,m)，从而时间空间都是 O(q\log n\log m) 的。

代码

注意 unordered_map 要防 hack。代码中的 dfs(n, m, i) 表示有多少个 0\le j<m 满足 S_j\oplus S_{j+n}\ne i.

// Let QwQ bless me. I love QwQ forever!

#include <stdio.h>
#include <stdint.h>
#include <utility>
#include <unordered_map>
#include <chrono>
#include <random>

#pragma GCC optimize("-Ofast")
#pragma GCC target("avx2")

using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;

struct hesh
{
    inline size_t operator()(std::pair<u64, u64> p) const
    {
        static const u64 r = std::chrono::high_resolution_clock().now().time_since_epoch().count();
        u64 x = p.first + p.second * r;
        x ^= r;
        x ^= (x >> 29);
        x *= 9;
        return x;
    }
};

std::unordered_map<std::pair<u64, u64>, u64, hesh> umap;

u64 solve(u64 n, u64 m, u64 i)
{
    if (i == 1) return m - solve(n, m, 0);
    if (m == 0) return 0;
    if (m == 1) return __builtin_parity(n) != 0;
    if (umap.count({n, m})) return umap[{n, m}];
    u64 ans = solve(n / 2, (m + 1) / 2, n % 2) + solve((n + 1) / 2, m / 2, n % 2);
    umap[{n, m}] = ans;
    return ans;
}

int main()
{
    int q; scanf("%d", &q);
    while (q--)
    {
        u64 n, m; scanf("%lld %lld", &n, &m);
        printf("%lld\n", solve(n, m, 0));
    }
}