题目链接：HDU 6596

你有一个正整数 $n$ 和一个六元组集合，我们定义六元组 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 的权值为 $\sum_{l_{x} \le x \le r_{x}, l_{y} \le y \le r_{y}, l_{z} \le z \le r_{z}} x \oplus y \oplus z$。

初始集合中只有一个元素 $(0, n - 1, 0, n - 1, 0, n - 1)$。接下来你要重复进行以下操作，直到集合的大小为 $n ^ 3$。

• 从集合中选择一个六元组 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 满足 $l_{x} < r_{x}$ 或 $l_{y} < r_{y}$ 或 $l_{z} < r_{z}$。

• 然后你需要从 $\{ x, y, z \}$ 中选择恰好一个元素，选择元素 $k$ 的条件是 $l_{k} < r_{k}$。

  • 如果你选择了 $x$，接下来你需要选择一个整数 $t \in [l_{x}, r_{x})$，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除，将 $(l_{x}, t, l_{y}, r_{y}, l_{z}, r_{z})$ 和 $(t +1, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。
  • 如果你选择了 $y$，接下来你需要选择一个整数 $t \in [l_{y}, r_{y})$，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除，将 $(l_{x}, r_{x}, l_{y}, t, l_{z}, r_{z})$ 和 $(l_{x}, r_{x}, t + 1, r_{y}, l_{z}, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。
  • 如果你选择了 $z$，接下来你需要选择一个整数 $t \in [l_{z}, r_{z})$，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, t)$ 和 $(l_{x}, r_{x}, l_{y}, r_{y}, t + 1, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。

请你求出可以获得的最大权值，答案对 $998244353$ 取模。

本题有多组数据。

数据范围：$1 \le n \le 10 ^ 6$，$1 \le \sum n \le 3 \times 10 ^ 6$。

Solution

我们把任意两个 $1 \times 1 \times 1$ 的立方体之间连边，边权为这两个立方体的权值之积。如果把 $A$ 切成 $B, C$ 则得到了 $B$ 和 $C$ 之间所有边的权值之积。由于所有边最终都会被割掉，则可以得到结论：最终的答案与选择方法无关。

显而易见的，答案的值为所有边权的和。设第 $i (1 \le i \le n ^ {3})$ 个单位立方体的权值为 $a_i$，则答案为 $\sum_{i = 1} ^ {n} \sum_{j = i + 1} ^ {n} a_{i} \cdot a_{j} = \frac{\left(\sum_{i = 1} ^ {n} a_{i}\right) ^ {2} - \sum_{i = 1} ^ {n} a_{i} ^ 2}{2}$。

$a_i$ 的数量很多，但是不同的值很少，于是我们只需要使用 $\text{FWT}$ 统计每种值的个数。

时间复杂度：$\mathcal O(\sum n \log n)$。

Code

#pragma GCC optimize("Ofast", "inline")

#include <cstdio>
#include <algorithm>
#include <vector>

typedef std::vector<int> Vec;

const int MOD = 998244353, I2 = (MOD + 1) >> 1;

void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += MOD);
}
int add(int x) {
    return x >= MOD ? x - MOD : x;
}
int sub(int x) {
    return x < 0 ? x + MOD : x;
}
namespace FWT {
    int extend(int x) {
        int n = 1;
        for (; n < x; n <<= 1);
        return n;
    }
    void transAnd(Vec &A, bool opt) {
        int n = A.size();
        for (int l = 2; l <= n; l <<= 1) {
            int m = l >> 1;
            for (int i = 0; i < n; i += l) {
                for (int j = 0; j < m; j++) {
                    if (opt) {
                        sub(A[i + j], A[i + j + m]);
                    } else {
                        add(A[i + j], A[i + j + m]);
                    }
                }
            }
        }
    }
    void transOr(Vec &A, bool opt) {
        int n = A.size();
        for (int l = 2; l <= n; l <<= 1) {
            int m = l >> 1;
            for (int i = 0; i < n; i += l) {
                for (int j = 0; j < m; j++) {
                    if (opt) {
                        sub(A[i + j + m], A[i + j]);
                    } else {
                        add(A[i + j + m], A[i + j]);
                    }
                }
            }
        }
    }
    void transXor(Vec &A, bool opt) {
        int n = A.size();
        for (int l = 2; l <= n; l <<= 1) {
            int m = l >> 1;
            for (int i = 0; i < n; i += l) {
                for (int j = 0; j < m; j++) {
                    int x = A[i + j], y = A[i + j + m];
                    if (opt) {
                        A[i + j] = 1LL * add(x + y) * I2 % MOD;
                        A[i + j + m] = 1LL * sub(x - y) * I2 % MOD;
                    } else {
                        A[i + j] = add(x + y);
                        A[i + j + m] = sub(x - y);
                    }
                }
            }
        }
    }
    Vec operator & (Vec A, Vec B) {
        int N = extend(std::max(A.size(), B.size()));
        A.resize(N), transAnd(A, false);
        B.resize(N), transAnd(B, false);
        for (int i = 0; i < N; i++) A[i] = 1LL * A[i] * B[i] % MOD;
        transAnd(A, true);
        return A;
    }
    Vec operator | (Vec A, Vec B) {
        int N = extend(std::max(A.size(), B.size()));
        A.resize(N), transOr(A, false);
        B.resize(N), transOr(B, false);
        for (int i = 0; i < N; i++) A[i] = 1LL * A[i] * B[i] % MOD;
        transOr(A, true);
        return A;
    }
    Vec operator ^ (Vec A, Vec B) {
        int N = extend(std::max(A.size(), B.size()));
        A.resize(N), transXor(A, false);
        B.resize(N), transXor(B, false);
        for (int i = 0; i < N; i++) A[i] = 1LL * A[i] * B[i] % MOD;
        transXor(A, true);
        return A;
    }
    void print(Vec A, char mid = ' ') {
        int n = A.size();
        for (int i = 0; i < n; i++) printf("%d%c", A[i], i == n - 1 ? '\n' : mid);
    }
};
using namespace FWT;

int n;

int main() {
    for (; scanf("%d", &n) == 1; ) {
        Vec A(n);
        std::fill(A.begin(), A.end(), 1);
        n = extend(n);
        A.resize(n), transXor(A, false);
        for (int i = 0; i < n; i++) A[i] = 1LL * A[i] * A[i] % MOD * A[i] % MOD;
        transXor(A, true);
        int s1 = 0, s2 = 0;
        for (int i = 0; i < n; i++) {
            add(s1, 1LL * i * A[i] % MOD);
            add(s2, 1LL * i * i % MOD * A[i] % MOD);
        }
        printf("%d\n", 1LL * sub(1LL * s1 * s1 % MOD - s2) * I2 % MOD);
    }
    return 0;
}