一开始读错题了以为给的是每一段的异或和
如果是异或和也能做
那就按位考虑,将所有段排序,若存在两段的左/右端点相同(如 \([l, r1],[l, r2]\))就断成 \([l, r1], [r1+1, r2]\)
于是从小到大枚举字段,树状数组查询区间异或和,若与给定不同就修改区间内的第一个位置使之相同
每个段都唯一对应一个“第一个位置”,所以可以构造出一个合法序列
按位拆开DP即可
现在给的是区间或了,可以参考官方题解
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long
//#define int long long
char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
int ans=0, f=1; char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
return ans*f;
}
int n, m, tem;
const ll mod=1e9+7;
inline ll qpow(ll a, ll b) {ll ans=1; for (; b; a=a*a%mod,b>>=1) if (b&1) ans=ans*a%mod; return ans;}
signed main()
{
int t=read();
while (t--) {
n=read(); m=read(); tem=0;
for (int i=1; i<=m; ++i) read(), read(), tem|=read();
printf("%lld\n", tem*qpow(2, n-1)%mod);
}
return 0;
}