题解：AT_arc205_e [ARC205E] Subset Product Problem

· · 题解

前置芝士：值域分块、少量集合论（主要是为了方便表示）。

以下我们将数以二进制形式表示为一个集合。 即：

若一个数二进制表示为 (1001)_2，那么它从低到高第 1 位和第 4 位为 1，则它表示集合 \{1,4\}。

由于符号 \subset 存在歧义，下文用 \subseteq 表示“包含于”，\subsetneq 表示“真包含于”。

根据以上形式，题目要求的可以转化为以下形式：

\prod_{1\le i\le k,a_i \subseteq a_k}a_i

我们将每一个 a_i 分成高 10 位 p_i 和低 10 位 q_i，即 a_i=p_i\times 2^{10}+q_i。

下面我们进行值域分块。我们考虑依据 q（p 也可以）对值域 2^{20} 进行分块，每块 1024 个数，共 1024 块。

接下来我们考虑如何维护每一个块的信息。记 f_{p,q} 为，高 10 位 p_i 满足 p_i\subseteq p，且低 10 位 q_i 满足 q_i=q 的 a_i 的乘积。即：

f_{p,q}=\prod_{1\le i\le n,p_i\subseteq p,q_i=q} a_i

接下来我们只需要实现插入操作和查询操作就可以求出答案了。

我们进行插入 a_k 的操作时，我们只需要维护块内的信息，即枚举每个满足 p_k \subseteq p 的 p（p_k 的超集），而 q_k 保持不变，然后更新 f_{p, q_k}。

进行查询操作的时候，我们查询满足条件的块，即枚举满足 q\subseteq q_k 的 q（q_k）的子集，然后统计 f_{p_k, q}。

插入和查询复杂度均为 O(2^{10})，总时间复杂度为 O(2^{10}n)。

最后注意除了左移右移以外的位运算（或、与、异或）优先级小于逻辑符号，需要括号。

code:

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

using ll = long long;

const ll N = 5e4 + 5, M = 1 << 10, P = 998244353;

int n;
ll f[M][M];// 分块数组

void init() {}

void solve()
{
    cin >> n;
    // 初始化
    for (int i = 0; i < 1 << 10; ++i)
    {
        for (int j = 0; j < 1 << 10; ++j)
            f[i][j] = 1;
    }
    for (int i = 1; i <= n; ++i)
    {
        ll x, p, q, res = 1;
        cin >> x;
        // 拆位
        p = x >> 10;
        q = x & ((1 << 10) - 1);
        // 插入，枚举 p 的超集
        for (int j = 0; j < 1 << 10; ++j)
        {
            if ((p | j) == j)
                (f[j][q] *= x) %= P;
        }
        // 查询，枚举 q 的子集
        for (int j = 0; j < 1 << 10; ++j)
        {
            if ((j | q) == q)
                (res *= f[p][j]) %= P;
        }
        cout << res << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int _ = 1;
    // cin >> _;
    init();
    while (_--)
        solve();
    return 0;
}