专栏文章

题解：P13275 [NOI2025] 集合

PPetit_Souris
P13275题解参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miout4dx
此快照首次捕获于
2025/12/03 01:30
3 个月前
此快照最后确认于
2025/12/03 01:30
3 个月前
查看原文
场上约 1h 通过此题，退役之战的高光时刻。一直训练的计数水平确实在这题上表现出来了，只可惜这 day 2 没有给我乘胜追击的机会，翻盘失败。
考虑枚举 SS，计算 f(P)=f(Q)=Sf(P) = f(Q) = S 的方案数。直观的想法是进行容斥：枚举集合 U⊇S,V⊇SU\supseteq S, V \supseteq S，钦定 f(P)f(P) 中所有在 UU 中的位为 11，f(Q)f(Q) 中所有在 VV 中的位为 11。
这样一个 (U,V)(U, V) 对 SS 的贡献系数为 (−1)pop(U)+pop(V)−2pop(S)(-1)^{\mathrm{pop(U) + pop(V) - 2pop(S)}}。(U,V)(U, V) 的方案数容易计算：考虑所有的 ii，如果 ii 同时是 U,VU, V 的超集，那么方案数为 1+2ai1 + 2a_i；如果是 U,VU, V 其中一个的超集，方案数为 1+ai1 + a_i；否则方案数为 11。把所有 ii 的方案数乘起来即可。
这样已经可以做到 O(8n)\mathcal O(8 ^ n) 了。
优化的想法很自然：考虑交换枚举顺序，先枚举 U,VU, V，这时候可能产生贡献的 SS 必须是 U and VU\ \mathrm{and}\ V 的子集。现在和 SS 有关的只有容斥系数，这个数只和 pop(U and V)\mathrm{pop}(U\ \mathrm{and}\ V) 有关。
求 (U,V)(U, V) 的方案数可以通过研究性质 B 想到一个方法：记 fSf_S 表示 SS 所有超集的 (1+ai)(1 + a_i) 的乘积，gSg_S 表示 SS 所有超集的 (1+2ai)(1 + 2a_i) 的乘积。显然权值为 fUfVgU or V\frac{f_Uf_V}{g_{U \ \mathrm{or}\ V}}。因此容易优化到 O(4n)\mathcal O(4 ^ n)。进一步地，pop(U and V)=pop(U)+pop(V)−pop(U or V)\mathrm{pop}(U\ \mathrm{and}\ V) = \mathrm{pop}(U) + \mathrm{pop}(V) - \mathrm{pop}(U \ \mathrm{or} \ V)，因此容易用 or - FWT 优化至 O(2nn)\mathcal O(2 ^ nn)。
最后需要考虑一下 ai=998244352a_i = 998244352 如何处理。考虑扩域，对每个值记录二元组 (k,v)(k, v) 表示乘上了 kk 个 00，显然对于每个 SS 只有最小的 kk 有效。容易发现 FWT 可以进行，因为具有可加性。而 IFWT 需要减法，看似会出现问题，但是实际上容易分析出正确性，因为如果 (k1,v1)(k_1, v_1) 减 (k2,v2)(k_2, v_2) 时，一定有 k2≥k1k_2 \ge k_1，且 k2>k1k_2>k_1 时不产生贡献。因此正确性得证，问题在 O(2nn)\mathcal O(2 ^nn) 时间复杂度内完美解决。
复现的代码：
CPP
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const ll Mod = 998244353;
ll n, a[(1 << 20) + 9];
ll pw(ll x, ll p) {
    ll res = 1;
    while(p) {
        if(p & 1) res = res * x % Mod;
        x = x * x % Mod, p >>= 1;
    }
    return res;
}
ll Add(ll x, ll y) {
    return ((x += y) >= Mod) ? (x - Mod) : (x);
}
ll Sub(ll x, ll y) {
    return ((x -= y) < 0) ? (x + Mod) : (x);
}
pii operator + (const pii &a, const pii &b) {
    if(a.first ^ b.first) return min(a, b);
    return {a.first, Add(a.second, b.second)};
}
pii operator - (const pii &a, const pii &b) {
    if(a.first ^ b.first) return a;
    return {a.first, Sub(a.second, b.second)};
}
pii operator * (const pii &a, const pii &b) {
    return {a.first + b.first, a.second * b.second % Mod};
}
pii f[(1 << 20) + 5], g[(1 << 20) + 5];
ll pw2[25], ipw2[25];
void FWT(pii *f) {
    for(ll i = 1; i < (1 << n); i <<= 1) {
        for(ll j = 0; j < (1 << n); j += (i << 1)) {
            rep(k, 0, i - 1) f[j + k + i] = f[j + k + i] + f[j + k];
        }
    }
}
void IFWT(pii *f) {
    for(ll i = 1; i < (1 << n); i <<= 1) {
        for(ll j = 0; j < (1 << n); j += (i << 1)) {
            rep(k, 0, i - 1) f[j + k + i] = f[j + k + i] - f[j + k];
        }
    }
}
ll pc(ll n) {
    return __builtin_popcount(n);
}
void solve() {
    n = read();
    rep(i, 0, (1 << n) - 1) a[i] = read();
    rep(i, 0, (1 << n) - 1) {
        if(a[i] != Mod - 1) {
            f[i] = {0, (1 + a[i]) % Mod};
            g[i] = {0, (1 + a[i] + a[i]) % Mod * pw((1 + a[i]) * (1 + a[i]) % Mod, Mod - 2) % Mod};
        }
        else {
            f[i] = {1, 1};
            g[i] = {2, Mod - 1};
        }
    }
    for(ll i = 1; i < (1 << n); i <<= 1) {
        for(ll j = 0; j < (1 << n); j += (i << 1)) {
            rep(k, 0, i - 1) {
                f[j + k] = f[j + k] * f[j + k + i];
                g[j + k] = g[j + k] * g[j + k + i];
            }
        }
    }
    rep(i, 0, (1 << n) - 1) {
        if(pc(i) & 1) f[i].second = Mod - f[i].second;
        f[i].second = f[i].second * pw2[pc(i)] % Mod;
    }
    FWT(f);
    rep(i, 0, (1 << n) - 1) f[i] = f[i] * f[i];
    IFWT(f);
    ll ans = 0;
    rep(i, 0, (1 << n) - 1) {
        if(f[i].first ^ g[i].first) continue;
        ans = (ans + f[i].second * g[i].second % Mod * ipw2[pc(i)]) % Mod;
    }
    write(ans), putchar('\n');
}
bool Med;
int main() {
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    ll T = read(); T = read();
    pw2[0] = 1;
    rep(i, 1, 22) pw2[i] = pw2[i - 1] * 2 % Mod;
    rep(i, 0, 22) ipw2[i] = pw(pw2[i], Mod - 2);
    while(T--) solve();
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...