题解：P13275 [NOI2025] 集合

· · 题解

好难啊。

设 N=\bigcup\limits_{i=0}^{n-1}\{i\}，\text{val}(S)=\prod\limits_{i\in S}a_i，由于 P\cap Q=\varnothing，故 \text{val}(P\cup Q)=\text{val}(P)\text{val}(Q)。先把贡献拆到每个 f(P) 上：

\begin{aligned} \text{answer}&=\sum_{S\subseteq N}\sum_{\substack{P\subseteq2^N\\f(P)=S}}\sum_{\substack{Q\subseteq2^N\\f(Q)=S\\P\cap Q=\varnothing}}\text{val}(P\cup Q)\\ &=\sum_{S\subseteq N}\sum_{\substack{P\subseteq2^N\\f(P)=S}}\text{val}(P)\sum_{\substack{Q\subseteq2^N\\f(Q)=S\\P\cap Q=\varnothing}}\text{val}(Q) \end{aligned}

元素的交集恰好为 S 不太好做，为了方便写成 FWT 需要的形式，考虑使用超集反演：

\sum_{\substack{P\subseteq2^N\\f(P)=S}}\text{val}(P)=\sum_{S\subseteq T\subseteq N}(-1)^{|T|-|S|}\sum_{\substack{P\subseteq 2^N\\T\subseteq f(P)}}\text{val}(P)

代入原式：

\begin{aligned} \text{answer}&=\sum_{S\subseteq N}\sum_{S\subseteq T_P\subseteq N}(-1)^{|T_P|-|S|}\sum_{\substack{P\subseteq 2^N\\T_P\subseteq f(P)}}\text{val}(P)\sum_{S\subseteq T_Q\subseteq N}(-1)^{|T_Q|-|S|}\sum_{\substack{Q\subseteq 2^N\\T_Q\subseteq f(Q)\\P\cap Q=\varnothing}}\text{val}(Q) \end{aligned}

发现两个 (-1)^{|S|} 抵消掉了，剩下的就是 (-1)^{|T_P|+|T_Q|}。然后交换求和符号，改为最外层枚举 T_P,T_Q：

\begin{aligned} \text{answer}&=\sum_{T_P,T_Q\subseteq N}(-1)^{|T_P|+|T_Q|}\sum_{S\subseteq T_P\cap T_Q}\sum_{\substack{P\subseteq 2^N\\T_P\subseteq f(P)}}\text{val}(P)\sum_{\substack{Q\subseteq 2^N\\T_Q\subseteq f(Q)\\P\cap Q=\varnothing}}\text{val}(Q) \end{aligned}

这时候 S 就被架空了，直接就是 2^{|T_P\cap T_Q|}，现在柿子变成了这样：

\begin{aligned} \text{answer}&=\sum_{T_P,T_Q\subseteq N}(-1)^{|T_P|+|T_Q|}2^{|T_P\cap T_Q|}\sum_{\substack{P\subseteq 2^N\\T_P\subseteq f(P)}}\text{val}(P)\sum_{\substack{Q\subseteq 2^N\\T_Q\subseteq f(Q)\\P\cap Q=\varnothing}}\text{val}(Q) \end{aligned}

考虑后面那一坨东西是在干什么，设 F_P 为 T_P 的所有父集构成的集合，同样定义 F_Q。那么原求和条件就变成了 P\subseteq F_P 和 Q\subseteq F_Q。

考虑每个 R\subseteq N 对答案的贡献。可以发现若 R\in F_P\cap F_Q，则 R 可以选择在 P 或 Q 中，也可以不选，故贡献为 2a_R+1；否则若 R\in F_P\Delta F_Q（\Delta 表示集合对称差），可以选择在 P 或 Q 的其中之一，也可以不选，故贡献为 a_R+1；否则不能在 P 或 Q 中，没有贡献（贡献为 1）。

因此原式化为：

\begin{aligned} \text{answer}&=\sum_{T_P,T_Q\subseteq N}(-1)^{|T_P|+|T_Q|}2^{|T_P\cap T_Q|}\prod_{R\in F_P\cap F_Q}(2a_R+1)\prod_{R\in F_P\Delta F_Q}(a_R+1) \end{aligned}

不妨设 A_S=\prod\limits_{S\subseteq T}(2a_T+1)，B_S=\prod\limits_{S\subseteq T}(a_T+1)，考虑用 A,B 来表示后面这一坨东西，把对称差拆开来，由于 F_P\cap F_Q 就是 T_P\cup T_Q 的全体父集，可以发现其实就是 \dfrac{A_{T_P\cup T_Q}B_{T_P}B_{T_Q}}{B^2_{T_P\cup T_Q}}。

进一步地，观察所求式的结构，不难想到设 C_S=\dfrac{A_S}{2^{|S|}B^2_S}，D_S=(-1)^{|S|}2^{|S|}B_S，原式化为：

\begin{aligned} \text{answer}&=\sum_{T_P,T_Q\subseteq N}C_{T_P\cup T_Q}D_{T_P}D_{T_Q}\\ &=\sum_{T\subseteq N}C_T\sum_{T_P\cup T_Q=T}D_{T_P}D_{T_Q} \end{aligned}

这是一个 OR 卷积的形式，直接上 FWT 即可。

但这样做有一个问题：分母上出现了 B，而 B 的定义中出现了 a_R+1，当 a_R=998244352 时会出现除数为 0 的情况，但此时答案又是存在的。

因此需要记录每个数乘/除了多少个 0，即以 x\times 0^z 的形式记录，并定义其运算，最后得到 0^0 的部分的和就是答案。

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar_unlocked()
il int rd() { int x = 0; char c = 0; while (c < '0' || c > '9') c = gc; while (c >= '0' && c <= '9') x = x * 10 - '0' + c, c = gc; return x; }
typedef long long ll;
const int N = 1 << 20 | 5, p = 998244353, inv2 = p + 1 >> 1;
int task_id, T, ppc[N], invpw2[21], _n, n, a[N];
int qpow(int a, int b) { int c = 1; while (b) { if (b & 1) c = (ll)c * a % p; a = (ll)a * a % p, b >>= 1; } return c; }
struct num { int x, z; num(int a = 0) { if (a) x = a, z = 0; else x = 1, z = 1;  } num(int x, int z): x(x), z(z) {} } A[N], B[N], invB[N], C[N], D[N], E[N];
il num operator+(num a, num b) { return a.z == b.z ? num((a.x + b.x) % p, a.z) : (a.z < b.z ? a : b); }
il num operator-(num a, num b) { return a.z == b.z ? num((a.x - b.x + p) % p, a.z) : (a.z < b.z ? a : num((p - b.x) % p, b.z)); }
il num operator*(num a, num b) { return num((ll)a.x * b.x % p, a.z + b.z); }
il num inv(num a) { return num(qpow(a.x, p - 2), -a.z); }
il num operator/(num a, num b) { return a * inv(b); }
void sufmul(num a[]) {
    for (int i = 0; i < _n; i++) {
        for (int j = 0; j < n; j++) if (!(j >> i & 1)) a[j] = a[j] * a[j ^ 1 << i];
    }
}
void FWT(num a[]) {
    for (int i = 0; i < _n; i++) {
        for (int j = 0; j < n; j++) if (j >> i & 1) a[j] = a[j] + a[j ^ 1 << i];
    }
}
void iFWT(num a[]) {
    for (int i = _n - 1; ~i; i--) {
        for (int j = 0; j < n; j++) if (j >> i & 1) a[j] = a[j] - a[j ^ 1 << i];
    }
}
void solve() {
    _n = rd(), n = 1 << _n;
    for (int i = 0; i < n; i++) a[i] = rd(), A[i] = num((a[i] << 1 | 1) % p), B[i] = num((a[i] + 1) % p);
    sufmul(A), sufmul(B);
    for (int i = 0; i < n; i++) invB[i] = inv(B[i]);
    for (int i = 0; i < n; i++) C[i] = A[i] * invB[i] * invB[i] * invpw2[ppc[i]];
    for (int i = 0; i < n; i++) D[i] = B[i] * (1 << ppc[i]) * (ppc[i] & 1 ? p - 1 : 1);
    FWT(D);
    for (int i = 0; i < n; i++) E[i] = D[i] * D[i];
    iFWT(E);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        num x = C[i] * E[i];
        if (!x.z) ans = (ans + x.x) % p;
    }
    cout << ans << '\n';
}
int main() {
    // freopen("set.in", "r", stdin), freopen("set.out", "w", stdout);
    for (int i = 1; i < N; i++) ppc[i] = ppc[i ^ (i & -i)] + 1;
    invpw2[0] = 1; for (int i = 1; i <= 20; i++) invpw2[i] = (ll)invpw2[i - 1] * inv2 % p;
    task_id = rd(), T = rd(); while (T--) solve();
}