P11458 Solution

irris · 2025-04-07 09:36:07 · 题解

下文先给出一个传统的 FWT 视角做法，再给出一个使用转置原理理解下的做法。

令 P(x) 表示 x 的 \operatorname{popcount}。随即，有 \sum\limits_{j=1}^n \frac{P(a_i\&a_j)}{P(a_i\mid a_j)} = P(a_i)\sum\limits_{j=1}^n \frac{1}{P(a_i\mid a_j)} + \sum\limits_{j=1}^n \frac{P(a_j)}{P(a_i\mid a_j)} - n。

首先，可以想到一个 O(n + 2^kk^2) 的做法：

不妨对每个 0 \leq s \leq k，求出有多少个 j 满足 P(a_i\mid a_j) = s。我们以类似的手法求出 \sum P(a_j)[P(a_i\mid a_j) = s]。
令 b_k = \sum_j [a_j = k]，对 b 做高维后缀和，保留 \operatorname{popcount} 恰好为 s 的元素后，再做高维前缀和，在 a_i 处统计对应的答案。
这个做法会算重，算重的原因在于我们可能实际上枚举到了 a_i\mid a_j 的超集，但对每种 a_i 再做一次二项式反演即可正确处理所有贡献。

为了优化复杂度至 O(n + 2^kk)，我们考虑不对每个 s 拆分做，而整体处理之。

\begin{aligned} f_x &= \sum_y \sum_S [(x\mid y) = S]c_y \cdot \frac{1}{P(S)}\\ &= \sum_y c_y \sum_T [(x\mid y) \subseteq T] \sum_{S \supseteq T} (-1)^{\lvert S\rvert - \lvert T\rvert}\frac{1}{P(S)} \end{aligned}

上一步使用了一个经典的容斥技巧：(x \mid y) 恰好为 S 是难以计算的，但如果 (x\mid y) \subseteq T，便只需要满足 x \subseteq T \land y \subseteq T，这里 x, y 变得独立。后面求和式的本质相当于

\sum_S \frac{1}{P(S)} [(x\mid y) \subseteq S] {\color{orange}(1 + (-1))^{\lvert S\rvert - \lvert(x\mid y)\rvert}} = \sum_S \frac{1}{P(S)} \sum_{T \subseteq S} [(x\mid y) \subseteq T] (-1)^{\lvert S\rvert - \lvert T\rvert},

对其交换求和顺序即得。

此时，位运算卷积技巧已经足以帮助我们解决这个问题：使用高维后缀和，对每个 T 求出 w_T 表示 \sum_{T \subseteq S} (-1)^{\lvert S\rvert - \lvert T\rvert} \frac{1}{P(S)}；将 c_y 做高维前缀和，点乘 w，最后做高维前缀和即得到 f。

int main() {
    int n = read<int>(), k = read<int>(), z = (1 << k);
    for (int i = 0; i < z; ++i) 
        pop[i] = __builtin_popcount(i);
    for (int j = 1; j <= k; ++j)    
        iv[j] = modint(j).inverse();
    for (int i = 1; i <= n; ++i) {
        x[i] = read<int>();
        c[x[i]] += 1, d[x[i]] += pop[x[i]];
    }
    for (int j = 1; j < z; ++j) 
        w[j] = modint(pop[j] & 1 ? -1 : 1) * iv[pop[j]];
    for (int i = 0; i < k; ++i) 
        for (int j = 0; j < z; ++j) if ((j >> i) & 1)
            w[j ^ (1 << i)] += w[j];
    for (int j = 0; j < z; ++j) 
        w[j] *= modint(pop[j] & 1 ? -1 : 1);
    auto process = [&](modint c[], modint w[]) -> void {
        for (int i = 0; i < k; ++i) 
            for (int j = 0; j < z; ++j) if ((j >> i) & 1) 
                c[j] += c[j ^ (1 << i)];
        for (int j = 0; j < z; ++j) 
            c[j] *= w[j];
        for (int i = 0; i < k; ++i) 
            for (int j = 0; j < z; ++j) if ((j >> i) & 1) 
                c[j ^ (1 << i)] += c[j];
    };
    process(c, w), process(d, w); 
    for (int i = 1; i <= n; ++i) 
        print<int>((modint(pop[x[i]]) * c[x[i]] + d[x[i]] - n).get(), '\n');
    return 0;
}

考虑我们所求为一向量 c，考察一任意向量 \boldsymbol w，\boldsymbol{c^T \cdot w} 即为 \sum_{i,j} w_ia_jb_{i\mid j}，使用 FWT 卷积即可；显然，如果我们能够提取每个 w_i 对应的贡献系数，即可求出每个 c_i。这里的「转置原理」则相当于一种技巧，原先的线性问题写作若干基本矩阵乘积后相当于建出了分层 DAG，而 原问题的计算形式是考察每个 \boldsymbol{w_i} 到达终点的方案数 并求和，我们 将 DAG 反向 得到的就是终点到每个 w_i 的方案数。

这种理解的本质是：在一个线性问题里，如果计算输出向量的与任意向量的内积结果是可行的，则可以相同的时间复杂度解决原问题。

int main() {
    int n = read<int>(), k = read<int>(), z = (1 << k);
    for (int j = 0; j < z; ++j) 
        pop[j] = __builtin_popcount(j), inv[j] = pop[j].inverse();
    for (int i = 1; i <= n; ++i) 
        a[i] = read<int>(), buc[a[i]] += 1, bucp[a[i]] += pop[a[i]];
    auto conv = [&](modint res[], modint a[], modint b[]) -> void {
        for (int j = 0; j < k; ++j) for (int i = 0; i < z; ++i) 
            if ((i >> j) & 1) a[i] += a[i ^ (1 << j)];
        for (int i = 0; i < z; ++i) bb[i] = b[i];
        for (int j = 0; j < k; ++j) for (int i = 0; i < z; ++i) 
            if (!((i >> j) & 1)) bb[i] -= bb[i ^ (1 << j)];
        for (int i = 0; i < z; ++i) 
            res[i] = a[i] * bb[i];
        for (int j = 0; j < k; ++j) for (int i = 0; i < z; ++i) 
            if (!((i >> j) & 1)) res[i] += res[i ^ (1 << j)];
    };
    conv(c, buc, inv), conv(d, bucp, inv);
    for (int i = 1; i <= n; ++i) 
        print<int>((pop[a[i]] * c[a[i]] + d[a[i]] - n).get(), '\n');
    return 0;
}