cf1614C. Divan and bitwise operations

C. Divan and bitwise operations

题意：有一个长度为n的序列，有m条信息 l r k ，指该序列从l到r所有元素 或(or) 起来为k。
求该序列所有子序列的异或和(xor)的代数和。

思路：
对于每一位，若区间或为$0$，那么一定每个元素都为$0$。
序列做差分，如果该区间为或1，那么$c[l]+1$，$c[r+1]?1$。如果为0，$c[l]+inf$，$c[r+1]?inf$。
对c做前缀和得到完整序列，对每一位考虑，只有奇数个1和若干个0才能对答案有贡献。设有p个1，q个0，即$ans+=(C_p^1+C_p^3+C_p^5+...)?2^q?2^n=2^{p?1}?2^q?2^n$（p!=0）。
p!=0时，$2^{p?1}?2^q=2^{n?1}$，故可以不用计算原序列，只考虑某一位上有没有1，直接计算ans。

#include<bits/stdc++.h>
using namespace std;#define read(x) scanf("%d",&x)
#define ll long long
#define maxn ((int)2e5)#define md ((long long)1e9+7)
#define inf maxnint n,m;
ll c[maxn+5][30];	//差分
bool a[maxn+5][30];ll quickpower(ll a,ll b) {
    ll ans=1;while(b) {
    if(b&1) ans=ans*a%md;a=a*a%md,b>>=1;}return ans%md;
}int main() {
    int T;cin>>T;while(T--) {
    cin>>n>>m;for(int i=1;i<=n;i++) for(int j=0;j<30;j++) a[i][j]=0,c[i][j]=0;for(int i=1;i<=m;i++) {
    int l,r,k;cin>>l>>r>>k;for(int j=0;j<30;j++) {
    int d=1<<j;if(k&d) {
    c[l][j]++,c[r+1][j]--;} else c[l][j]-=inf,c[r+1][j]+=inf;}}for(int i=1;i<=n;i++) {
    for(int j=0;j<30;j++) {
    c[i][j]+=c[i-1][j];if(c[i][j]>0) a[i][j]=1;else a[i][j]=0;}}ll ans=0;for(int j=0;j<30;j++) {
    int p=0,q=0;for(int i=1;i<=n;i++) {
    if(a[i][j]) p++;else q++;}if(p) ans=(ans+quickpower(2,j)*quickpower(2,p-1)%md*quickpower(2,q))%md;}cout<<ans<<endl;} return 0;
} 

#include<bits/stdc++.h>
using namespace std;#define read(x) scanf("%d",&x)
#define ll long long
#define maxn ((int)2e5)#define md ((long long)1e9+7)
#define inf maxnint n,m;ll quickpower(ll a,ll b) {
    ll ans=1;while(b) {
    if(b&1) ans=ans*a%md;a=a*a%md,b>>=1;}return ans%md;
}int main() {
    int T;cin>>T;while(T--) {
    cin>>n>>m;ll ans=0;for(int i=1;i<=m;i++) {
    int l,r,k;cin>>l>>r>>k;ans|=k;}ans=ans*quickpower(2,n-1)%md;cout<<ans<<endl;} return 0;
}