P10583 题解

· · 题解

前言

时间复杂度不是最优，但个人感觉更容易想的做法。

思路

首先不难看出题目生成的图是一个树形结构。设树有 k 层，则前 k - 1 层的点数是 O(\sqrt{n}) 量级的。另外，树上边权的异或和同样为 O(\sqrt{n}) 量级。

考虑根号分治，设立阈值 B (B \ge \sqrt{n})，先对于编号 x \le B 的点，暴力算出从根到该点的异或值，然后开一个数组 val 统计每个值出现的次数。

然后处理编号 x > B 的点，不难发现其父亲到根路径上的异或和为已知。于是直接 O(n) 枚举第 k 层（也就是最后一层）节点对应边权然后统计异或值，然后再 O(\sqrt{n} \log n) 异或卷积即可。总时间复杂度 O(n)。也许可以通过，但不够优秀。

优化

上述做法的瓶颈在于需要 O(n) 枚举最后一层的边权。进一步观察发现，编号为 x 的点与其子节点间存在以下简单规律：

对于第 k - 1 层和第 k 层间的边，2x 的最小值为 O(\sqrt[4]{n}) 量级，最大值为 O(\sqrt{n}) 量级。

考虑分块，设块长为 b(b \le \sqrt{B})。对于一个块 [p, p + b - 1]，可以将所有满足 2x > p + b - 1 的节点 x 对应的异或值与 [p, p + b - 1] 内的边权做异或卷积。这个操作每个块的复杂度为 O(\sqrt{n} \log n)，总复杂度为 O(\frac{n}{b} \log n)。而对于 2x \in (p, p + b - 1] 的节点 x，则可以暴力处理。这部分复杂度为 O(b \sqrt{n})。

不难发现取 B = \sqrt{n}, b = \sqrt[4]{n} 时复杂度最优。总复杂度 O(n^{\frac{3}{4}} \log n)。



#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1000000, mod = 998244353, L = (1 << 16);
int n, S, val[N + 10], sq[N + 10], f[4 * N + 10], A[4 * N + 10], B[4 * N + 10], C[4 * N + 10], d[N + 10];
inline int x2(int x){
    return x * x;
}

inline int ksm(int u, int v){
    int mul = 1;
    while(v){
        if(v & 1) mul = mul * u % mod;
        u = u * u % mod, v >>= 1;
    }
    return mul;
}

inline void fwt(int *f, int len, int opt){
    for(int i = 1; i < len; i <<= 1)
        for(int j = 0; j < len; j += (i << 1))
            for(int k = 0; k < i; k++){
                int x = f[j + k], y = f[i + j + k];
                f[j + k] = x + y, f[i + j + k] = x - y;
                if(!opt) f[j + k] >>= 1, f[i + j + k] >>= 1;
    }
}

int dfs(int x){
    if(x == 1 || val[x]) return val[x];
    return val[x] = (dfs(sq[x]) ^ (x - x2(sq[x])));
}

signed main (){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    S = sqrt(n);
    for(int i = 1; x2(i) <= N; i++) sq[x2(i)] = i;
    for(int i = 1; i <= N; i++){
        if(!sq[i])
            sq[i] = sq[i - 1];
        val[i] = dfs(i);
    }
    if(n <= N) for(int i = 1; i <= n; i++) f[val[i]]++;
    else{
        for(int i = 1; i <= N; i++) f[val[i]]++;
        int sq = 1000, pos = sq, len = 2000, ls = 1, lst = sq, Max = 0;
        for(int i = sq; x2(i) <= n; i++){
            d[i] = x2(i + 1) - x2(i);
            A[val[i]]++;
            pos = i;
        }
        A[val[pos]]--;
        Max = d[pos - 1];
        for(int i = len; i < Max; i += len, ls += len){
            for(int j = ls; j <= i; j++) B[j] = 1;
            fwt(A, L, 1);
            fwt(B, L, 1);
            for(int j = 0; j < (L); j++) C[j] = A[j] * B[j];
            fwt(A, L, 0);
            fwt(B, L, 0);
            fwt(C, L, 0);
            for(int j = 0; j < (L); j++) f[j] += C[j];
            for(int j = ls; j <= i; j++) B[j] = 0;
            for(int j = lst; j < pos; j++)
                if(d[j] <= i + len){
                    A[val[j]]--;
                    lst = j + 1;
                }
            if(i + len >= Max) break; 
        }
        int sum = N - 1;
        for(int i = sq; i < pos; i++){
            int P = d[i] / len;
            sum += d[i];
            for(int j = P * len + 1; j < d[i]; j++)
                f[val[i] ^ j]++;
        }
        for(int i = sq + 1; i < pos; i++) f[val[i] ^ 0]++;
        for(int i = 0; i <= d[pos] && sum < n; i++, sum++) f[val[pos] ^ i]++; 
    }
    fwt(f, L, 1);
    for(int i = 0; i < L; i++) f[i] = x2(f[i]);
    fwt(f, L, 0);
    int ans = 1;
    for(int i = 1; i < L; i++) ans = ans * ksm(i, f[i] >> 1) % mod;
    cout << ans << '\n';
    return 0;
}