专栏文章

题解：AT_arc205_e [ARC205E] Subset Product Problem

____PatrickChen___
AT_arc205_e题解参与者 1已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@minyuipe
此快照首次捕获于
2025/12/02 10:35
3 个月前
此快照最后确认于
2025/12/02 10:35
3 个月前
查看原文
前置芝士：值域分块、少量集合论（主要是为了方便表示）。
以下我们将数以二进制形式表示为一个集合。 即：
若一个数二进制表示为 (1001)2(1001)_2，那么它从低到高第 11 位和第 44 位为 11，则它表示集合 {1,4}\{1,4\}。
由于符号 ⊂\subset 存在歧义，下文用 ⊆\subseteq 表示“包含于”，⊊\subsetneq 表示“真包含于”。
根据以上形式，题目要求的可以转化为以下形式：
∏1≤i≤k,ai⊆akai\prod_{1\le i\le k,a_i \subseteq a_k}a_i
我们将每一个 aia_i 分成高 1010 位 pip_i 和低 1010 位 qiq_i，即 ai=pi×210+qia_i=p_i\times 2^{10}+q_i。
下面我们进行值域分块。我们考虑依据 qq（pp 也可以）对值域 2202^{20} 进行分块，每块 10241024 个数，共 10241024 块。
接下来我们考虑如何维护每一个块的信息。记 fp,qf_{p,q} 为，高 1010 位 pip_i 满足 pi⊆pp_i\subseteq p，且低 1010 位 qiq_i 满足 qi=qq_i=q 的 aia_i 的乘积。即：
fp,q=∏1≤i≤n,pi⊆p,qi=qaif_{p,q}=\prod_{1\le i\le n,p_i\subseteq p,q_i=q} a_i
接下来我们只需要实现插入操作和查询操作就可以求出答案了。
我们进行插入 aka_k 的操作时，我们只需要维护块内的信息，即枚举每个满足 pk⊆pp_k \subseteq p 的 pp（pkp_k 的超集），而 qkq_k 保持不变，然后更新 fp,qkf_{p, q_k}。
进行查询操作的时候，我们查询满足条件的块，即枚举满足 q⊆qkq\subseteq q_k 的 qq（qkq_k）的子集，然后统计 fpk,qf_{p_k, q}。
插入和查询复杂度均为 O(210)O(2^{10})，总时间复杂度为 O(210n)O(2^{10}n)。
最后注意除了左移右移以外的位运算（或、与、异或）优先级小于逻辑符号，需要括号。
code:
CPP
#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;
}

评论

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

正在加载评论...