ZR1153

首先我们可以发现一个比较简单的容斥做法

直接暴力枚举\(2^m\)个限制强制不合法,算贡献

注意如果两个限制冲突那么答案为0

直接暴力差分就好了

这样就有了快乐的\(30\)分了

接下来考虑对容斥进行DP

把所有点区间按照右端点排序,如果出来两个颜色相同的区间一个包含了另外一个,那么大区间是没有用的,因为小区间满足条件大区间一定满足

我们设\(f_{i}\)表示满足第\(i\)个限制的带容斥系数的方案数

那么转移我们就枚举上一个没有交的区间

\[f_{i} =g_{;_i -1} + \sum_{co_i = co_j,l_j\ge r_i}f_j
\]

其中\(g_x\)表示\(1-x\)位置满足\(1-x\)的所有容斥之后的限制的前缀和

也就是说

\[g_i = g_{i - 1}\times s + \sum_{r_j = i}f_j
\]

就是看看第\(i\)位置上的限制满足还是不满足综合考虑的前缀和

继续回到求\(f_i\)的式子

既然\(i\)的这个限制要容斥,那么强制他不被满足,前面就是对所有和他没有交的限制求一个总的容斥

后面算有交的部分的贡献,必须满足和当前限制的颜色相同,

我们排序之后,有交的集合是一个区间,我们二分找到对应位置维护前缀和即可

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<vector>

#include<ctime>

#include<cmath>

#include<set>

#include<map>

#define LL long long

#define pii pair<int,int>

#define mk make_pair

#define fi first

#define se second

using namespace std;

const int N = 4e5 + 3;

const LL mod = 998244353;

struct seg{

	int li,ri;

	int xi;

}a[N],b[N];

vector <pii> co[N];

vector <LL> h[N];

LL f[N],g[N];

int n,m,s,cnt;

inline int read(){

	int v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

inline bool cmp(seg x,seg y){

	return x.ri < y.ri || (x.ri == y.li && x.li > y.li);

}

inline LL find(int x,int rr){

//	printf("%d %d\n",x,rr);

	int l = 0,r = h[x].size() - 1,ans = -1;

	if(r < 0) return 0;

	while(l <= r){

		int mid = (l + r) >> 1;

		if(co[x][mid].se < rr) l = mid + 1,ans = mid;

		else r = mid - 1;

	}

//	printf("%d %d %d %lld\n",l,r,ans,ans == -1 ? h[x].back() : h[x].back() - h[x][ans]);

	return ans == -1 ? h[x].back() : h[x].back() - h[x][ans];

}

inline LL mo(LL x){

	if(x >= mod) x-= mod;

	return x;

}

int main(){

	n = read(),m = read(),s = read();

	for(int i = 1;i <= m;++i){

		a[i].li = read();

		a[i].ri = read();

		a[i].xi = read();

	}

	sort(a + 1,a + m + 1,cmp);

	for(int i = 1;i <= m;++i){

		bool flag = 0;

		if(!co[a[i].xi].size()) co[a[i].xi].push_back(mk(a[i].li,a[i].ri));

		else{

			pii x = co[a[i].xi].back();

			if(x.fi >= a[i].li && x.se <= a[i].ri) flag = 1;

			else co[a[i].xi].push_back(mk(a[i].li,a[i].ri));

		}

		if(!flag) b[++cnt] = a[i];

	}

	m = cnt;

	memcpy(a,b,sizeof(a));

//	puts("new::");

//	for(int i = 1;i <= m;++i) cerr << a[i].li << " " << a[i].ri << " " << a[i].xi << endl;

//	puts("next::");

	int now = 1;

	f[0] = g[0] = 1;

	for(int i = 1;i <= m;++i){

	//	cerr << "dsdas::"<< a[i].li << " " << a[i].ri << " " << a[i].xi << endl;

		for(;now < a[i].ri;now++) g[now] = (g[now] + g[now - 1] * s) % mod;

		f[i] = (-g[a[i].li - 1] + mod);

		f[i] -= find(a[i].xi,a[i].li);

		if(f[i] < 0) f[i] += mod;

		LL gg = h[a[i].xi].empty() ? 0 : h[a[i].xi].back();

		h[a[i].xi].push_back(mo(gg + f[i]));

		g[a[i].ri] = mo(g[a[i].ri] + f[i]);

	}

	for(;now <= n;++now) g[now] = (g[now] + g[now - 1] * s) % mod;

	printf("%lld\n",g[n]);

	return 0;

}

巴特西

ZR1153

ZR1153

最新文章

热门文章