JZOJ5892. 【NOIP2018模拟10.4】矿石

题解

关键问题是如何避免跟之前的重复。
首先，现将所以的采矿点排序。
对于一个采矿点，它不能只选择与它前面一个相邻的采矿点公共的矿来采，
因为这样会跟前一个采矿点重复。
所以，对于一个采矿点，必须至少选一个在前面完全没有出现过的采矿点。
设第i个采矿点与前面所有采矿点不同矿数为$x_i$xi​，与前面一个采矿点相同的数目是$y_i$yi​
那么这个采矿点贡献的方案数就是$(2^{x_i}-1)*2^{y_i}$(2xi​−1)∗2yi​

code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long
#define N 100003
#define M 103
#define P putchar
#define G getchar
using namespace std;
char ch;
void read(int &n)
{
	n=0;
	ch=G();
	while((ch<'0' || ch>'9') && ch!='-')ch=G();
	ll w=1;
	if(ch=='-')w=-1,ch=G();
	while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
	n*=w;
}

const int mo=998244353;
int l[N],r[N],a[N],s[N];
int n,m,sum[N],id1,id2;
ll ans;

ll ksm(ll x,int y)
{
	ll s=1;
	for(;y;y>>=1,x=x*x%mo)
		if(y&1)s=s*x%mo;
	return s;
}

int main()
{
	freopen("ore.in","r",stdin);
	freopen("ore.out","w",stdout);
	
	read(n);read(m);
	for(int i=1;i<=n;i++)
		read(l[i]),read(r[i]);
	for(int i=1;i<=m;i++)read(a[i]);
	sort(a+1,a+1+m);
	
	for(int i=1;i<=n;i++)
	{
		id1=lower_bound(a+1,a+1+m,l[i])-a;
		id2=upper_bound(a+1,a+1+m,r[i])-a;
		if(a[id1]<=r[i])s[id1]++;
		if(id1<id2)sum[id1+1]++,sum[id2]--;
	}
	
	for(int i=1;i<=m;i++)
	{
		sum[i]=sum[i-1]+sum[i];
		ans=(ans+(ksm(2,s[i])-1+mo)%mo*ksm(2,sum[i])%mo)%mo;
	}
	
	printf("%lld",ans);
	
	return 0;
}