CF1906K Deck-Building Game

题目链接：https://codeforces.com/problemset/problem/1906/K

题意

有大小为 $n$ 的多重集 $A$。求找到两个不相交子集，使它们各自的异或和相等的方案数。

很容易将其转换为求如下值：

$$ \sum_{S \subset A} 2 ^ {|S|} \cdot [\oplus_{x \in S} x = 0] $$

解法（官解）

构造多项式 $F$，使得 $F_i(A) = \sum_{S \subset A} 2 ^ {|S|} \cdot [\oplus_{x \in S} x = i]$，要求的结果是 $F_0(A)$。

那么 $F$ 满足如下特性：$F(A \cup B) = F(A) \oplus F(B)$，其中 $\oplus$ 代表多项式的异或卷积。

对只包含同一个数的集合，容易求出多项式只包含两项：

$$ F(\set{i} \cdot n) = a_0 + a_i \cdot x^i, a_i = \dfrac{1}{2} ((-1)^n + 3^n), a_0 = 3^n - a_i $$

记 $U = 2^{\lceil \log\max{A}\rceil}$，则卷积合并所有多项式即可得到答案，时间复杂度 $O(U^2 \log U)$。

考虑采用分治卷积优化时间复杂度。记 $G(l,r)$ 为所有 $i \in [l,r)$ 对应多项式的卷积，可以观察到如下性质：

• 若采用分治法计算，则一定有 $r - l = 2^b, l \equiv r \equiv 0 \mod 2^b$；
• $G(l,r)$ 中所有项的次数落在区间 $[0, r-l)$ 和 $[l, r)$ 内。

因此，分治的每一层只需维护两个次数小于 $r-l$ 的多项式，合并时计算四次卷积即可。根据主定理可得时间复杂度为 $O(U \log^2 U)$。

代码实现（C++)

constexpr int M = 1 << 17;
using P = pair<int, vector<Z>>;
using A = array<P, 2>;
void solve() {
    int n;
    cin >> n;
    vector<int> cnt(M);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    function<A(int, int)> calc = [&](int l, int r) -> A {
        if (r - l == 1) {
            A res;
            res[0] =
                pair{0, vector<Z>{(-Z(-1).pow(cnt[l]) + Z(3).pow(cnt[l])) / 2}};
            res[1] =
                pair{l, vector<Z>{(Z(-1).pow(cnt[l]) + Z(3).pow(cnt[l])) / 2}};
            return res;
        } else {
            A res;
            vector<Z> RP1(r - l, 0), RP2(r - l, 0);
            int mid = (l + r) >> 1;
            A a1 = calc(l, mid), a2 = calc(mid, r);
            for (auto [base1, P1] : a1) {
                for (auto [base2, P2] : a2) {
                    int base = base1 ^ base2;
                    auto Pn = XOR_convolution(P1, P2);
                    if (base >= l) {
                        for (int i = 0; i < (int)Pn.size(); i++) {
                            RP2[(i ^ base) - l] += Pn[i];
                        }
                    } else {
                        for (int i = 0; i < (int)Pn.size(); i++) {
                            RP1[i ^ base] += Pn[i];
                        }
                    }
                }
            }
            return {pair{0, RP1}, {l, RP2}};
        }
    };
    A res = calc(0, M);
    cout << res[0].second[0] + res[1].second[0] << "\n";
}