Codeforces Round #757 Div.2 C.Divan and bitwise operations 组合数学

Problem Analysis

题目机翻：有一次，Divan分析了一个由 n n n非负整数组成的序列 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1​,a2​,…,an​，如下所示。他考虑了序列 a a a的每个非空子序列，计算了其元素的位XOR，并将所有的XOR相加，得到了序列 a a a的惬意度。如果 c c c可以通过删除几个（可能是零或全部）元素从 d d d中得到，那么序列 c c c就是序列 d d d的子序列。例如， [ 1 ,   2 ,   3 ,   4 ] [1, \, 2, \, 3, \, 4] [1,2,3,4], [ 2 ,   4 ] [2, \, 4] [2,4]和 [ 2 ] [2] [2]是 [ 1 ,   2 ,   3 ,   4 ] [1, \, 2, \, 3, \, 4] [1,2,3,4]的子序列，但 [ 4 ,   3 ] [4, \, 3] [4,3]和 [ 0 ] [0] [0]不是。 Divan对他的分析非常自豪，但现在他失去了序列 a a a，还有舒适度值! 然而，迪凡记得序列 a a a的 m m m连续子段上的bitwise OR的值。事实证明，原始序列的每个元a素都至少包含在这 m m m段中的一个。Divan要求你利用他记忆中的信息帮助找到序列 a a a的舒适度。如果可能有几个舒适度值，请打印任何一个。由于结果可能非常大，请打印 1 0 9 + 7 10^9+7 109+7的模值。

思路分析：

假设存在以下数列：
A 1 = a 0 m … a 0 i … a 03 a 02 a 01 a 00 A 2 = a 1 m … a 1 i … a 13 a 12 a 11 a 10 A 3 = a 2 m … a 2 i … a 23 a 22 a 21 a 20 … A n = a n m … a n i … a n 3 a n 2 a n 1 a n 0 A_1 = a_{0m} \dots a_{0i} \dots a_{03}a_{02}a_{01}a_{00}\\ A_2 = a_{1m} \dots a_{1i} \dots a_{13}a_{12}a_{11}a_{10}\\ A_3 = a_{2m} \dots a_{2i} \dots a_{23}a_{22}a_{21}a_{20}\\ \dots \\ A_n = a_{nm} \dots a_{ni} \dots a_{n3}a_{n2}a_{n1}a_{n0}\\ A1​=a0m​…a0i​…a03​a02​a01​a00​A2​=a1m​…a1i​…a13​a12​a11​a10​A3​=a2m​…a2i​…a23​a22​a21​a20​…An​=anm​…ani​…an3​an2​an1​an0​
对 30 30 30位而言，考虑每一位对答案的贡献：设 { a x i } \{a_{xi}\} {axi​}位置有 y y y个 1 1 1，由于取奇数个 1 1 1异或才会产生有效值( 1 1 1)。因此最后在加和中所占的子和一定为：
s u b s u m = 2 i × 2 n − x × ( 2 x − 2 x − 1 ) = 2 i × 2 n − 1 subsum = 2^i \times 2^{n - x} \times (2^x - 2^{x - 1}) = 2^i \times 2 ^ {n - 1} subsum=2i×2n−x×(2x−2x−1)=2i×2n−1
那么将所有的数字或起来，然后对非零位计数求和即可。

也可以分位计数统计，最后累加答案。

Accepted Code

#include 
#define int long long
#define ll long long
using namespace std;
const int N = 2e5 + 10, mod = 1e9 + 7;
int a[N];
int bit[40];

inline ll bin(ll x, ll n, ll MOD, ll ret = 1) {
    for (x %= MOD; n; n >>= 1, x = x * x % MOD) if (n & 1) ret = ret * x % MOD;
    return ret == 1 ? 0 : ret;
}

inline void solve(){
    memset(bit, 0, sizeof(bit));
    int n, m; cin >> n >> m;
    int res = bin(2, n - 1, mod), ans = 0;
    res = 1;
    for(int i = 1; i  l >> r >> x;
        for (int j = 0; j > j & 1;
    }
    for (int i = 0; i