CF1614C Divan and bitwise operations

点我点我

正解思路

首先对于 \(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;
 }
上一篇:出错提示AttributeError: 'str' object has no attribute 'decode'解决方法


下一篇:Grpc.Core.RpcException: Status(StatusCode=DeadlineExceeded, Detail="Deadline Exceeded")