Codeforces-1614 C: Divan and bitwise operations

Codeforces-1614 C: Divan and bitwise operations Codeforces-1614 C: Divan and bitwise operations

题目传送门：Codeforces-1614
题目友情链接：LeetCode-1863

题目 题目截图

样例描述

题目大意

  定义一个数组的舒适度为其中每一个子序列（子序列指在原数组中删除一部分得到的有序序列）的 X O R XOR XOR 值的总和。现在给出这个数组一些段的 O R OR OR 值，数组中的每个数都会出现在其中一些段中，问该数组的舒适度。

题目解析

  本题要想做的快，需要利用一些 X O R XOR XOR 的性质。
  设数组 a a a 的长度为 n n n，简单来说，数组 a a a 的舒适度就等于 2 n − 1 × O R ( a ) 2^{n-1} times OR(a) 2n−1×OR(a)，其中 O R ( ⋅ ) OR(sdot) OR(⋅) 代表将数组内的元素直接全部求 O R OR OR。显然，对本题来说，区间不重要了，因为答案利用的是整个数组的 O R OR OR 值。
  我们可以分析一下为什么是这样，由于除了加法以外的 *** 作都是位独立的，可以分别考虑每个二进制位对舒适度计算最终求和的贡献。
  我们直接假设在第 i i i 个二进制位，数组中有 k ≥ 1 k ge 1 k≥1 个二进制位是 1 1 1 的数，对应地，有 n − k n-k n−k 个为 0 0 0。那么对子序列的选择，我们有 2 n 2^n 2n 种情况，但若要求其中异或值第 i i i 个二进制位为 1 1 1 的话，必然需要在这 k k k 个对应位为 1 1 1 的数中选择奇数个。显然总的选择方式是 2 n − 1 2^{n-1} 2n−1 （具体地，选择 0 0 0 有 2 ( n − k ) 2^{(n-k)} 2(n−k) 种，选择 1 1 1 有 C k 1 + C k 3 + ⋯ + C k f i n a l _ o d d = 2 k − 1 C_k^1+C_k^3+cdots +C_k^{final_odd}=2^{k-1} Ck1​+Ck3​+⋯+Ckfinal_odd​=2k−1，二者相乘），同时考虑每种情况，在第 i i i 位对求和的贡献是 2 i 2^i 2i，因此第 i i i 位对最终的总贡献是 2 n − 1 × 2 i 2^{n-1}times 2^i 2n−1×2i。如果整个数组任何元素第 i i i 位没有 1 1 1，显然该位对最终的求和没有贡献。
  因此，我们将数组中有 1 1 1 的二进制位对最终求和的贡献公式写出，并提出 2 n − 1 2^{n-1} 2n−1，可以得到 s u m = 2 n − 1 × ∑ i 2 i [ ∃ j , i -th bit of   a j = 1 ] = 2 n − 1 × O R ( a ) sum=2^{n-1} times sum_i 2^i[exist j,itext{-th bit of} , a_j =1] = 2^{n-1}times OR(a) sum=2n−1×∑i​2i[∃j,i-th bit ofaj​=1]=2n−1×OR(a)。

Code

#include 
using namespace std;

const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;
int n, m, l, r, x;

int main(){
    int t, OR, pow;
    cin >> t;
    while(t--) {
        cin >> n >> m;
        OR = 0, pow = 1;
        while(m--) cin >> l >> r >> x, OR |= x;
        for(int i=1; i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5610627.html