Educational Codeforces Round 84 (Rated for Div. 2)F. AND Segments

技术文章 6个月前 完美者
1,229 0

标签:space   while   ++   codeforce   答案   math   ace   tps   ems   

题意:提问有多少个长度为n的a集合0<a<\(2^k\),满足\(l_i\)\(r_i\)的区间&的值为\(x_i\)
原题链接
题解:最首先就是要拆位,对于&操作来说每一位是分开的,dp[i][j]表示是前i位最近的一个0在j位的方案数,
从第i为到第i+1位时,假如z到i+1位有一个是0,则dp[i+1][0~z-1]会被消为0,如果不是就可以继承第i位时的状态,而dp[i+1][i+1]会成为dp[i][0]到dp[i][i]的累加和
假如只能是1,dp[i+1][0~i]继承上一位的状态,而dp[i+1][i+1]=0。
最终的答案是\(\sum_{j=0}^{n}\)dp[n][j]
我们i从1遍历到n,每次sum的值为\(\sum_{j=0}^{n}\)dp[i][j]
pre[i]存储的是前一个最近的数x,使得x到i中至少有一个0
当i这个数只能为0时,把pre[i]之前的还没有清零的dp都清0,也就是sum要减去以前的这些dp值
等于1时,sum要翻倍,具体看代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define mod 998244353
#define ll long long
struct node{
	int l,r,x;
}a[500100];
int pre[500100],flag[500100],dp[500100];
int n,k,m;
int solve(int z){
	int t=(1<<z);
	memset(pre,0,sizeof(pre));
	memset(flag,0,sizeof(flag));
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=m;i++){
		if((a[i].x&t)!=0){
			flag[a[i].l]++;
			flag[a[i].r+1]--;
		}
		else{
			pre[a[i].r]=max(pre[a[i].r],a[i].l);
		}
	}
	for(int i=1;i<=n;i++)flag[i]+=flag[i-1];
	int last=0;
	int sum=1;
	dp[0]=1;
	for(int i=1;i<=n;i++){
		if(flag[i]==0){
			dp[i]=sum;
			sum=2*sum%mod;
		}
		while(last<pre[i]){
			sum=(sum-dp[last]+mod)%mod;
			last++;
		}
	}
	return sum;
}
int main(){
	scanf("%d %d %d",&n,&k,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&a[i].l,&a[i].r,&a[i].x);
	}
	ll ans=1;
	for(int i=0;i<k;i++){
		ans=(ans*solve(i))%mod;
	}
	printf("%lld\n",ans);
}

Educational Codeforces Round 84 (Rated for Div. 2)F. AND Segments

标签:space   while   ++   codeforce   答案   math   ace   tps   ems   

原文地址:https://www.cnblogs.com/League-of-cryer/p/14270059.html

版权声明:完美者 发表于 2021-01-14 10:46:55。
转载请注明:Educational Codeforces Round 84 (Rated for Div. 2)F. AND Segments | 完美导航

暂无评论

暂无评论...