每日构造题训练——C. Divan and bitwise operations

每日构造题训练

题目链接: 题目传送门

前置知识: 按位或运算

一、题意:

$1$、 有一个长度为$n$的但是元素未知的数组$a$, 给定$m$个约束，每个约束都有$l,r,x$, 并且满足$1\le l\le r\le n,1\le x<2^{30},a[l]|a[l+1]|....|a[r]=x$, $l$是按位或，要求构造出$a$的$n$个元素，使得其满足$m$个约束并且$0\le a[i]<2^{30}$，并且求出每个非空子序列(子序列可以不连续,但是要保序)的异或值之和，结果模$1e9+7$, 保证在这些约束下有解。
$2$、数据范围: $1\le n\le 2e5$, $1\le m\le 2e5$

二、题解：

$1$、 我们先思考 $|$ 运算的性质，可以知道只要在区间中有一个数字在某个二进制位上是$1$，那么区间的$|$值一定在此二进制位上有$1$，那么我们不妨倒着思考，假设我们知道一个区间的$|$值，我们就可以知道它们在哪些二进制一定是$0$, 怎么根据这些区间记录呢，我们可以用预处理的思想去做，因为暴力去更新显然会超时。
$2$、我们可以开一个数组$cnt[30][i]$用来标记第i个数字上的第$30$个二进制位，当我们读取到查询$l,r,x$时, 我们将数字$x$中二进制位为$0$的位置找到，假设是$j$,那么我们就可以用差分处理， $cnt[j][l]+=1,cnt[j][r+1]-=1$，最后我们就可以用前缀和知道每个数字的每一个二进制位的信息了，此时我们不妨将每一位的初值赋值为$(1<<30)-1$，这样每一个二进制位都有$1$，当我们知道$cnt[j][i]>0$, 则 $a[i]\&=(1<<j)$。
$3$、根据上面设计的思路我们可以找到满足约束的数组$a$的每个元素，接下来我们要计算所有的非空子序列异或值之和，我们不妨考虑一下累积每个二进制位的贡献，我们先统计一下每个二进制位的个数$count[i]$,让我们来推导一下计算二进制位贡献的公式，首先只有奇数个$1$异或值才能是$1$, 所以，我们将很轻易的推导出计算贡献的公式: $\sum (C(\genfrac{}{}{0ex}{}{1}{count[i]})\ast 2^{n-1}+C(\genfrac{}{}{0ex}{}{3}{count[i]})\ast 2^{n-3}+...+C(\genfrac{}{}{0ex}{}{2\ast x+1}{count[i]})\ast 2^{n-(2\ast x+1)})$。
$4$、时间复杂度(忽略常数): $O(N\ast 30+N\ast log(2^{30}-1))$。

三、代码实现:

涉及算法：快速幂、组合数预处理、差分、前缀和、逆元。

#include <bits/stdc++.h>
#define int long long 
#define ff first 
#define ss second 
using namespace std; 
using PII = pair<int, int>; 
constexpr int N = 2e5 + 10; 
constexpr int inf = 0x3f3f3f3f;
constexpr int mod = 1e9 + 7; 
int n, m; 
int a[N]; 
int cnt[40][N];
int us[40]; 
int f1[N], f2[N]; 
int qmi(int x, int y) {int res = 1; while(y) {if(y & 1) res = res * x % mod; x = x * x % mod; y >>= 1; }return res; 
}int md(int a, int b) {return (f1[a] * f2[a - b] % mod * f2[b] % mod) % mod; 
}
void solve() {scanf("%lld%lld",&n,&m);// for(int j = 0; j < 40; j ++ ) us[j] = 0; for(int i = 1; i <= n; i ++ ) a[i] = (1 << 30) - 1; for(int i = 0; i < 30; i ++ ) { us[i] = 0; for(int j = 1; j <= n; j ++ ) cnt[i][j] = 0;}for(int i = 1; i <= m; i ++ ) {int l, r, x; scanf("%lld%lld%lld",&l,&r,&x);for(int j = 0; j < 30; j ++ ) {if(x >> j & 1) continue; cnt[j][l] += 1, cnt[j][r + 1] -= 1; }}for(int i = 0; i < 30; i ++ ) {for(int j = 1; j <= n; j ++ ) cnt[i][j] += cnt[i][j - 1]; for(int j = 1; j <= n; j ++ ) if(cnt[i][j]) a[j] -= (1 << i);}for(int i = 1; i <= n; i ++ ) for(int j = 0; j < 30; j ++ ) if(a[i] >> j & 1) us[j] ++; for(int i = 0; i < 30; i ++ ) {int x = us[i], su = 0;  // us[i] = 0;for(int j = 1; j <= x; j += 2) su = (su + md(x, j) * qmi(2,n-x) % mod) % mod;us[i] = su;}int ans = 0; for(int i = 0; i < 30; i ++ ) ans = (ans + (1ll << i) * us[i] % mod) % mod;printf("%lld\n",ans);    
}signed main() {f1[0] = 1, f2[0] = 1; for(int i = 1; i < N; i ++ ) {f1[i] = (f1[i - 1] * i) % mod;  f2[i] = qmi(f1[i], mod - 2);}int ts; cin >> ts; while(ts -- ) solve(); return 0; 
}