codeforces 757-div2 C

题目

题意: 给定n、m。要求构造任意一个长度为n的满足题意的数组，满足对于所有给定的m个区间[l,r] x，满足[l,r]区间的数进行or运算以后为x。输出该数组的coziness,coziness为该数组的所有子序列的异或和之和。 思路: 直接懵逼，不知道咋构造,也不知道怎么算贡献。 两个关键点 1.求子序列的异或和之和: 从数位角度考虑，对于二进制第k位，如果有x个数在该位均为1，可以选出1、3、5…个数，使得该位产生2^(k-1)的贡献，毕竟偶数个1异或以后为0.可以证明，对于二进制中任意一位，有2的n-1个子序列包含奇数个该位。 那么，我们不需要关心具体的数组长什么样，只需要知道数组中是否存在一个数在二进制某一位有1即可。 证明:

2.构造满足题意的数组: 根据上述性质，我们不需要关心具体的数组长什么样，只需要知道数组中是否存在一个数在二进制某一位有1即可。只需要将所有给定区间的x or起来，即数组中最大的数x，根据他的值来决定二进制哪些位有1，这些位的1加起来也就是x本身。 所以答案为 ans * 2^(n-1) 时间复杂度: O(n)

代码:

// Problem: C. Divan and bitwise operations
// Contest: Codeforces - Codeforces Round #757 (Div. 2)
// URL: https://codeforces.com/contest/1614/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i>= 1;
	}
	return res % mod;
}
void solve()
{
   ans = 0;
   read(n); read(m);
   for(int i=0;i>T;
   read(T);
   while(T--)
   {
   	 solve();
   }
   return 0;
}