题目传送门
正解
思路
先考虑对于 x 的限制怎么处理。
因为 \(l \sim r\) 使用或来连接，所以如果 x 中的某一位是0，则要求该区间内的每一个数的这一位都得是 0 。
那么，先默认每个数的每一位都是 1 ，再用这 m 个限制搞一搞即可。
主要的难点在于统计答案。
首先，我们知道，对于每个子序列的答案的某一位，当且仅当有奇数个数的这一位是 1 ，然后选择 1 的方案就是 \(C^1_x+C^3_x+C^5_x+...+C^{x-(!(x\& 1))}_x\) （x 表示这一位的 1 的个数），而每一个 0 可选可不选，那么选 0 总方案就是 \(2^{n-x}\)。
显然，这样的复杂度是 \(\Theta(过不了)\)，需要进行优化。
组合数是有以下性质的：
-
\(C^m_n=C^{m-1}_{n-1}+C^{m}_{n-1}\)
-
\(\sum\limits^n_{i=0}C^i_n=2^n\)
根据性质 1，将 \(C^1_x+C^3_x+C^5_x+...+C^{x-(!(x\& 1))}_x\) 中的每一个组合数拆分，可以将其变成 \(\sum\limits^{x-1}_{i=0}C^i_{x-1}\) ，也就把它变成了 \(2^{x-1}\) ，最终的总选择方案就是 \(2^{x-1}\times 2^{n-x}\) ，其实这样就可以过了，不过你可以把它变成 \(2^{n-1}\) ，进行进一步优化。
这以后，最终答案就是 \(\sum\limits_{i=0}^n2^{n-1}\times 2^i\) ，然后将 \(2^{n-1}\) 提出来，得到 \(2^{n-1}\times \sum\limits_{i=0}^n2^i\) 不过显然我们算的是选 1 的方案，所以如果这一位没有就不计贡献。
等下，“这一位”指的是什么？其实就是将所有的 x 或 起来以后的“这一位”（我们把它称作 sum），那么很好理解，“这一位”是 0 不会产生贡献，而是 1 应该产生贡献，所以对于 “\(2^i\)” ，它需要乘上 \(2^{n-1}\) 以计入答案当且仅当 i “这一位”是 1 。
然后，这个就相当于将 \(2^{n-1}\) 乘上了一个 sum！！！
然后，l 和 r 就卵用没有了！！！
输出的时候，就只需要输出 \(2^{n-1} \times sum\) 了！！！
然后就做完了！！！
复杂度 \(\Theta(Tn)\) ！！！
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;const ll MO(1e9+7);ll T,n,m,sum,l,r,x,tww;
int main(){
scanf("%lld",&T);
while(T--){
tww=1;sum=0;scanf("%lld",&n,&m);
for(int i=1;i<n;++i) tww=(tww<<1)%MO;
for(int i=1;i<=m;++i){scanf("%lld%lld%lld",&l,&r,&x);sum|=x;}
printf("%lld\n",(1ll*sum*tww)%MO);
}
return 0;
}