CF1327F AND Segments

2021/8/13 6:06:25

本文主要是介绍CF1327F AND Segments,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

CF1327F AND Segments

不难想到按位考虑,把每一位选到最后的答案乘起来。

可以发现,假如一段区间 $and \ sum=x$,对于第 $i$ 位,假如 $(x>>i)\&1$ ,那么这一段必须这一位都是 $1$,否则至少要有一个 $0$。

那么我们先枚举第 $wei$ 位,那么如何确定 $a_i$ 的第 $wei$ 位是必须 $1$ 还是?我们发现,这东西就是个区间覆盖+覆盖完查询,无脑差分即可。

做到这里我就不会了,因为我想到 $dp$,设 $f[i][j]$ 为到第 $i$ 个数字,上一个 $0$ 的下标是 $j$。

但不会转移。

我们考虑,对于每一个点 $i$,它的上一个 $0$ 肯定不能乱选,且上一个 $0$ 是单调不降的。

考虑 $[l,r]$ 的操作这一位为 $0$,那么对于 $r+1$ 来说,它上一个 $0$ 可以选择 $[l,r]$,那么至少就是 $l$。

考虑记 $pos[i]$ 表示 $i$ 的上一个 $0$ 至少在 $pos[i]$ 处。

考虑转移 $f$,枚举 $i,j$。

1. $j<pos[i],f[i][j]=0$

2. $pos \le j<i,f[i][j]=f[i-1][j]$ 这里是因为这一段的假如 $i$ 填 $0$,那么上一个 $0$ 应该是 $i$,所以只能填 $1$,从前面转移即可。

3. $j=i,f[i][j]=\sum_{k=pos[i]}^{i-1}f[i-1][k]$ 假如上一个就是它本身,显然当前就是 $0$。

那么,这样会 $TLE$,怎么优化呢?

我们发现,实际上很多状态都是承接作用而已。干脆改下定义 $f[i]$ 为匹配到第 $i$ 个数字,上一个 $0$ 的下标是 $i$,那么每一个按 3 转移即可。注意 $pos$ 前面提到过单调不降,维护个清 0 指针维护操作 1。对于操作 2,因为定义改了,所以这一位不可能是 1。对于这一位强制必须 0 的情况,赋 0 即可。

要学到什么,对于二进制有关的题可以拆位看看,区间覆盖+全局查可以差分,状态太多无用可以考虑改定义。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <map>

#define ll long long

using namespace std;
int rd() {
	int f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}
ll lrd() {
	ll f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}

const int N=(int)(5e5+5),mod=998244353;
struct node {
	int l,r,x;
}P[N];
ll f[N],ans=1;
int pos[N],a[N],n,K,m;

ll sol(int wei) {
	memset(pos,0,sizeof(pos)); memset(a,0,sizeof(a)); memset(f,0,sizeof(f));
	for(int i=1;i<=m;i++) if((P[i].x>>wei)&1) a[P[i].l]++,a[P[i].r+1]--; else pos[P[i].r+1]=max(pos[P[i].r+1],P[i].l);
	for(int i=2;i<=n+1;i++) a[i]+=a[i-1],pos[i]=max(pos[i],pos[i-1]);
	f[0]=1;
	ll sum=1,l=0;
	for(int i=1;i<=n+1;i++) {
		while(l<pos[i]) sum-=f[l],f[l++]=0,sum%=mod;
		if(a[i]) f[i]=0; else f[i]=sum;
		sum+=f[i]; sum%=mod;
	//	cout<<f[i]<<endl;
	}
	//cout<<f[n+1]<<endl; 
	return f[n+1];
}

int main() {
	n=rd(); K=rd(); m=rd();
	for(int i=1;i<=m;i++) P[i].l=rd(),P[i].r=rd(),P[i].x=rd();
	for(int i=0;i<K;i++) ans=ans*sol(i)%mod;
	ans=(ans%mod+mod)%mod; printf("%lld",ans);
	return 0;
}

  



这篇关于CF1327F AND Segments的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程