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