首页 > 其他分享 >题解 CF1743F【Intersection and Union】

题解 CF1743F【Intersection and Union】

时间:2024-04-23 15:23:38浏览次数:26  
标签:matrix leq Union 题解 线段 矩阵 int Intersection op

posted on 2022-10-21 19:23:54 | under 题解 | source

problem

给定 \(n\) 个集合 \(S_i\),以 \(l_i,r_i\) 的形式给出,集合的元素就是 \(\{x|x\in [l_i,r_i]\cap \mathbb{N}\}\)。

有三种集合间的二元运算,分别是交(\(\cap\))、并(\(\cup\))、对称差(\(\oplus\))。

其中对称差(\(A\oplus B\))的定义是 \(\{x|x\in A,x\not\in B\text{或}x\in B,x\not\in A\}\)。

现在有 \(n-1\) 个未知的运算,\(op_1,op_2,\cdots,op_{n-1}\),每个 \(op_i\) 可以是交、并、对称差的任意一个。

请你对于 \(op_i\) 的 \(3^{n-1}\) 种设置方案,求出:

\[|(((S_1\ op_1\ S_2)\ op_2\ S_3)\ op_3\ S_4)\cdots\ op_{n-1}\ S_n| \]

之和。

其中 \(|A|\) 为集合 \(A\) 的大小。

\(2\leq n\leq 3\times 10^5,0\leq l_i,r_i\leq 3\times 10^5\)

solution 1

考虑每个元素(每个点)的贡献。

考虑枚举线段,使得这一位出现在答案中(为 \(1\))的方案数,令前面的 \(i-1\) 条线段的方案数为 \(f_{i,0},f_{i,1}\)。若这条线段覆盖/不覆盖,操作为或/并/异或(注意不覆盖的也要考虑其操作),推出 \(f\) 的转移式。

将 \(f\) 写作矩阵乘法之形式。假设我们已经有 \(M_1,M_2\) 两个转移矩阵(一个覆盖,一个不覆盖),当 \(L\leq j\leq R\) 时乘上一个矩阵,反之乘上另外一个矩阵。以线段树维护矩阵乘法之和(注意,矩阵有分配律),快速地用初始值乘上 \(f\) 求之。

对于一条线段,它左边乘同一个矩阵,中间乘一个,右边乘一个,于是扫描线之。亦可 以时间建树,强行堆叠线段,区间乘法。

solution 2

简化 solution 1,发现矩阵中的 \(\times 2\) 是相同的。我们只考虑某一位最后一个出现的线段,枚举前面是否出现,简化 \(f\) 的转移为一堆 \(2,3\) 的幂,故 \(O(n)\) 地解决了这个问题。

code

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <algorithm>
using namespace std;
typedef long long LL;
const int P=998244353;
template<int N,int M,class T=LL> struct matrix{
	T a[N+1][M+1];
	matrix(bool k=0){memset(a,0,sizeof a);for(int i=1;i<=N;i++) a[i][i]=k;}
	T* operator[](int i){return a[i];}
};
template<int N,int M,class T=LL> matrix<N,M,T> operator+(matrix<N,M,T> a,matrix<N,M,T> b){
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
			a[i][j]=(a[i][j]+b[i][j])%P;
	return a;
}
template<int N,int M,int R,class T=LL> matrix<N,R,T> operator*(matrix<N,M,T> a,matrix<M,R,T> b){
	matrix<N,R,T> r=0;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=R;j++)
			for(int k=1;k<=M;k++)
				r[i][j]=(r[i][j]+a[i][k]*b[k][j])%P;
	return r;
}
template<int N,class T=LL> matrix<N,N,T> operator^(matrix<N,N,T> a,LL b){
	matrix<N,N,T> r=1;
	for(;b;b>>=1,a=a*a) if(b&1) r=r*a;
	return r;
}
matrix<2,2> A,B,C,E,F;
template<int N> struct segtree{
	matrix<2,2> ans[N<<2];
	matrix<2,2> build(int p,int l,int r){
		if(l==r) return ans[p]=A;
		int mid=(l+r)>>1;
		return ans[p]=build(p<<1,l,mid)*build(p<<1|1,mid+1,r);
	}
	void modify(int x,matrix<2,2> k,int p,int l,int r){
		if(l==r) return ans[p]=k,void();
		int mid=(l+r)>>1;
		if(x<=mid) modify(x,k,p<<1,l,mid);
		else modify(x,k,p<<1|1,mid+1,r);
		ans[p]=ans[p<<1]*ans[p<<1|1];
	}
};
int n;
LL ans;
pair<int,int> a[600010];
segtree<300010> t;
int main(){
	A[1][1]=3,A[1][2]=0,A[2][1]=1,A[2][2]=2;
	B[1][1]=1,B[1][2]=2,B[2][1]=1,B[2][2]=2;
	C[1][1]=1,E=1,F[1][2]=1;
	scanf("%d",&n);
	t.build(1,1,n),t.modify(1,E,1,1,n);
	for(int i=1,l,r;i<=n;i++) scanf("%d%d",&l,&r),a[i]={l,i},a[i+n]={r+1,-i};
	sort(a+1,a+n*2+1);
	for(int i=0,pos=1;i<=3e5+10;i++){
		while(pos<=n*2&&a[pos].first==i){
			pair<int,int> q=a[pos++];
			if(abs(q.second)==1) t.modify(1,q.second<0?E:F,1,1,n);
			else t.modify(abs(q.second),q.second<0?A:B,1,1,n);
		}
		ans=(ans+(C*t.ans[1])[1][2])%P;
	}
	printf("%lld\n",ans);
	return 0;
}

标签:matrix,leq,Union,题解,线段,矩阵,int,Intersection,op
From: https://www.cnblogs.com/caijianhong/p/solution-CF1743F.html

相关文章

  • 【微电平台】-高并发实战经验-奇葩问题解决及流程优化之旅
    微电平台微电平台是集电销、企业微信等于一体的综合智能SCRMSAAS化系统,涵盖多渠道管理、全客户生命周期管理、私域营销运营等主要功能,承接了京东各业务线服务,专注于为业务提供职场外包式的一站式客户管理及一体化私域运营服务。 导读本文介绍电销系统【客户名单离线打标......
  • CF1863G Swaps 题解
    题目链接点击打开链接题目解法这么牛的题!!!先套路地建图,连边\(i\toa_i\)考虑交换\(a_i\)和\(a_{a_i}\)的含义,我们把边\(i\toa_i,\;a_i\toa_{a_i}\)变成了\(i\toa_{a_i}\)和\(a_i\)的自环每次交换的话分析过于复杂,考虑打\(tag\),我们把所有操作过的\(i\),在\(i......
  • Numb 题解
    前言五一网课的例题,但是网上没有题解,所以来写一篇,就当攒RP了。题目可以在这里提交。原题是Baekjoon-19083,但是交不了?题目简述给你一个偶数\(n\),求一个二进制数\(x=\overline{a_1a_2\dotsa_n}\),满足:\(x\equiv0\pmod{n}\);\(\foralli\in[1,n]\),\(\overline{......
  • CF1137F Matches Are Not a Child's Play 题解
    题目链接点击打开链接题目解法参考abruce的非\(lct\)的做法\(compare\)操作是搞笑的,可以转化成求\(u,v\)的\(when\)操作一个结论是编号最大的点一定是最晚删的,不妨令编号最大的点为根,则删除顺序一定是从下往上删的先考虑原树上单个点\(u\)的\(when\)怎么求令......
  • 字符型union注入
    注入目标和思路:拿到库名---拿到表名---拿到列名---拿到用户名和密码用id=1'orderbyx--+来确定表有几列,然后用id=0'unionselectx1,x1,x3--+来确定回显位,然后在更改回显位用database()来拿到数据库名,以下用sqlname表示。注:数据库系统的数据库information_schem......
  • wps使用FileDialog(msoFileDialogFolderPicker)问题解决
    在vba里面使用了WithApplication.FileDialog(msoFileDialogFolderPicker),在excel里面多次测试均正常,但在wps里面运行时,发现只有打开文档后第一次运行宏是正确的,之后运行就再取不到选取的单元格,不管怎么选取,.SelectedItems.Count都是0。百度搜索为什么。 找到两个帖子1、 ......
  • 牛客小白月赛91 题解
    A.Bingbong的化学世界签到题意:给你苯环的结构,判断类型。思路:按照区别特判即可。代码:#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.end()#defineendl'\n'#definedebug(x)c......
  • EasyPoi 导出xlsx下拉列表过长问题解决
    问题描述:通过EasyPoi导出Excel带下拉框字段时,下拉框内值超过255时,会报错Stringliteralsinformulascan'tbebiggerthan255charactersASCII解决方案:额外创建sheet页去存储下拉框内数据,然后从这个sheet页中读取下拉框数据存到下拉列表中,最后需将额外创建的sheet隐藏......
  • Two Sided Cards 题解
    前言五一网课的例题,但是网上没有详细的题解(真的连题解都找不到啊),所以来写一篇,就当攒RP了。题目可以在这里提交。原题是TopCoder-10947,但是有了账号也交不了?题目简述有\(n\)张卡片,正面和反面分别组成了\(1\simn\)的排列。现在你需要将这\(n\)张卡片排成一排。卡片......
  • P1168 题解
    P1168中位数-洛谷很巧妙的一个题,自己没想出来。用一个「对顶堆」来维护,即一个大根堆和一个小根堆。保证大根堆的队首\(\le\)小根堆的队首,并使他们的堆中元素的个数尽量相等。操作如下:每次加入一个元素时,如果这个数比大根堆的队首大,就加入小根堆;否则加入大根堆。比较两......