点我点我
正解思路
首先对于 \(x\) 的限制需要处理
因为 \(l \sim r\) 使用或运算,所以如果结果是 \(0\) ,必然所有数都是 \(0\)
我们可以默认所有数都为 \(1\) ,然后再用 \(m\) 个限制来决定放多少 \(0\)
于是开始统计答案
首先,as we all know,如果是偶数个 \(1\) , 他是无法产生贡献的 因此得出一个柿子:\(C^1_x + C^3_x + C^5_x + ... + C^{最后一个奇数}_x\)
考虑到 \(0\) 可选可不选,我们就又有 \(2^{n-x}\)中选法,把他们乘起来,最后在乘一个 \(2^i\),也就是第 \(i\) 位的贡献 然而这样会TLE
考虑组合数的两个性质:
\(C^n_m = C^{n-1}_{m-1} + C^n_{m-1}\)
\(\sum_{i=1}^n{C^i_n}\)
答案可以优化为 \(sum=2^{x-1}\)
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,mod=1e9+7;
int t;
long long po[233334];
int main()
{
cin >> t;
po[0]=1;
for(int i=1;i<=233333;++i) po[i]=(po[i-1]*2)%mod;
while(t--)
{
int sum=0;
int n,m,l,r,x;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) scanf("%d%d%d",&l,&r,&x),sum|=x;
long long ans=1ll*sum*po[n-1]%mod;
printf("%lld\n",ans);
}
return 0;
}