智乃酱的子集与超集

NC225630. 智乃酱的子集与超集

描述

智乃酱有 ${N}$ 个物品，并且第 ${i}$ 个物品的权值为 $a_i$ ，对于一个含有 ${k}$ 个物品集合 $U=\left \{ a_{p_{1}},a_{p_{2}},a_{p_{3}}...a_{p_{k}} \right \}$ ，我们定义集合 ${U}$ 的价值为 $a_{p_{1}}\oplus a_{p_{2}}\oplus a_{p_{3}}\oplus...\oplus a_{p_{k}}$ ，其中 $\oplus$ 表示异或运算。即定义一个集合的价值为：该集合所拥有的物品权值之异或和。

现在智乃酱想问你 ${M}$ 个问题，对于每个问题他都会给你一个 ${k}$ 个物品集合 ${U}$ ，他想让你告诉她 ${U}$ 的所有子集的价值之和， ${U}$ 的所有超集的价值之和。

在本问题中，全集的定义为这 ${N}$ 个物品组成的集合。

输入描述

第一行输入两个正整数表示智乃酱有个物品，个问题。
接下来一行个正整数表示物品的权值。
接下来行分别表示个问题。
每行第一个整数表示该查询中集合的元素个数，后面个正整数表示该集合中第个物品的编号为(下标从开始计算)。

输出描述

输出 ${M}$ 行，每行输出两个整数，中间用空格隔开。

对于每个集合 ${U}$ ，输出 ${U}$ 的所有子集的价值之和， ${U}$ 的所有超集的价值之和。

示例1

输入:

输出:

说明:

如果一个集合S2中的每一个元素都在集合S1中，且集合S1中可能包含S2中没有的元素，则集合S1就是S2的一个超集，反过来，S2是S1的子集。 S1是S2的超集

异或是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。其运算法则为：a⊕b = (¬a ∧ b) ∨ (a ∧¬b)如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 494ms, 内存消耗: 18832K, 提交时间: 2022-10-04 11:21:43

#include<iostream>
using namespace std;
typedef long long LL;
int n,m;
LL a[2000010],b[2000010];
int s[25];
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>s[i];
	for(int i=0;i<1<<n;i++){
		for(int j=0;j<n;j++){
			if(i>>j&1)a[i]^=s[j];
		}
		b[i]=a[i];
	}
	for(int j=0;j<n;j++){
		for(int i=0;i<1<<n;i++){
			if(i>>j&1)a[i]+=a[i^(1<<j)];
			else b[i]+=b[i^(1<<j)];
		}
	}
	while(m--){
		int k;
		int sum=0;
		cin>>k;
		for(int i=1;i<=k;i++){
			int p;
			cin>>p;
			sum+=1<<(p-1);
		}
		cout<<a[sum]<<" "<<b[sum]<<endl;
	}
    return 0;
}

上一题

下一题

详情