题解 CF1614C Divan and bitwise operations

传送门

一开始读错题了以为给的是每一段的异或和
如果是异或和也能做
那就按位考虑,将所有段排序,若存在两段的左/右端点相同(如 \([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;
}
上一篇:linux – 我可以使用并行端口作为CUPS输入设备吗?


下一篇:CF1614C Divan and bitwise operations