11.15 模拟 t3 rainbow
11.15 模拟 t3 rainbow
给出一个 \(n\) 个点 \(m\) 条边的图，每个点度数最多为 \(2\) . 第 \(i\) 个点颜色为 \(1\) 到 \(a_i\) .
如果有多少种染色的方法，使得相连的两个点颜色不相同 . 模 \(998244353\) .
\(1\leq m\leq n\leq 2\cdot 10^5,1\leq a_i\leq 2\cdot 10^5\)
如果是链的情况，就是
考虑如何求出环的，如果断掉一条边，就形成了环，但是第一个点和最后一个点的颜色可能相同 .
考虑容斥 ，把环上 \(a_i\) 最小的那个点放在链的开头 . 考虑环的结束最后 \(k\) 个点一定和开头相同 .
方案数就是链的方案数 - 开头和最后 \(1\) 个点相同的方案数 + 开头和最后 \(2\) 个点相同的方案数 - \(\cdots\)
时间复杂度 : \(O(n)/O(n\log n)\)
空间复杂度 : \(O(n)\)
code
#include
using namespace std;
const int N=2e5+10;
const int mod=998244353;
int n,m,mxv;
int a[N];
bool vis[N];
vectorg[N];
vectorv;
int ans=1;
class node{public:int val,sz,tg1,tg2;}ts[N<<2];
void build(int x,int l,int r){
if(l==r){
ts[x]=(node){0,1,0,0};
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
ts[x]=(node){0,ts[x<<1].sz+ts[x<<1|1].sz,0,0};
}
inline void pd(int x){
if(!ts[x].tg1&&!ts[x].tg2)return;
if(ts[x].tg1){
ts[x<<1].val=ts[x<<1|1].val=0;
ts[x<<1].tg1=ts[x<<1|1].tg1=1;
ts[x<<1].tg2=ts[x<<1|1].tg2=0;
ts[x].tg1=0;
}
if(ts[x].tg2){
ts[x<<1].val=(ts[x<<1].val+1ll*ts[x<<1].sz*ts[x].tg2%mod)%mod;
ts[x<<1|1].val=(ts[x<<1|1].val+1ll*ts[x<<1|1].sz*ts[x].tg2%mod)%mod;
ts[x<<1].tg2=(ts[x<<1].tg2+ts[x].tg2)%mod;
ts[x<<1|1].tg2=(ts[x<<1|1].tg2+ts[x].tg2)%mod;
ts[x].tg2=0;
}
}
void upd(int x,int l,int r,int cl,int cr,int val){
if(l==cl&&r==cr){
if(l!=r)pd(x);
ts[x].val=(ts[x].val+1ll*ts[x].sz*val%mod)%mod;
ts[x].tg2=(ts[x].tg2+val)%mod;
return;
}
pd(x);
int mid=(l+r)>>1;
if(cr<=mid)upd(x<<1,l,mid,cl,cr,val);
else if(mid+1<=cl)upd(x<<1|1,mid+1,r,cl,cr,val);
else upd(x<<1,l,mid,cl,mid,val),upd(x<<1|1,mid+1,r,mid+1,cr,val);
ts[x].val=(ts[x<<1].val+ts[x<<1|1].val)%mod;
}
void mdf(int x,int l,int r,int cl,int cr){
if(l==cl&&r==cr){
if(l!=r)pd(x);
ts[x].val=0;
ts[x].tg1=1;
ts[x].tg2=0;
return;
}
pd(x);
int mid=(l+r)>>1;
if(cr<=mid)mdf(x<<1,l,mid,cl,cr);
else if(mid+1<=cl)mdf(x<<1|1,mid+1,r,cl,cr);
else mdf(x<<1,l,mid,cl,mid),mdf(x<<1|1,mid+1,r,mid+1,cr);
ts[x].val=(ts[x<<1].val+ts[x<<1|1].val)%mod;
}
int qry(int x,int l,int r,int pos){
if(l==r)return ts[x].val;
pd(x);
int mid=(l+r)>>1;
if(pos<=mid)return qry(x<<1,l,mid,pos);
else return qry(x<<1|1,mid+1,r,pos);
}
void dfs(int x){
vis[x]=true;
v.push_back(x);
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i];
if(!vis[to]){
dfs(to);
}
}
}
void solv_line(){
mdf(1,1,mxv,1,mxv);
int tmp=1;
for(int i=0;i<(int)v.size();i++){
if(i==0)upd(1,1,mxv,1,a[v[i]],1);
else{
int val=ts[1].val;
if(a[v[i]]>=a[v[i-1]]){
if(a[v[i-1]]+1<=a[v[i]])
upd(1,1,mxv,a[v[i-1]]+1,a[v[i]],(mod-val)%mod);
upd(1,1,mxv,1,a[v[i-1]],(mod-val)%mod);
}else{
mdf(1,1,mxv,a[v[i]]+1,a[v[i-1]]);
upd(1,1,mxv,1,a[v[i]],(mod-val)%mod);
}
tmp=-tmp;
}
}
int res=(ts[1].val*tmp+mod)%mod;
ans=1ll*ans*res%mod;
}
void solv_cycle(){
mdf(1,1,mxv,1,mxv);
int mn=mxv+1,id=-1;
for(int i=0;i<(int)v.size();i++)if(a[v[i]]vec;
for(int i=id;i<(int)v.size();i++)vec.push_back(v[i]);
for(int i=0;ires;
int tmp=1;
for(int i=0;i<(int)v.size();i++){
if(i==0)upd(1,1,mxv,1,a[v[i]],1);
else{
int val=ts[1].val;
if(a[v[i-1]]<=a[v[i]]){
if(a[v[i-1]]+1<=a[v[i]])
upd(1,1,mxv,a[v[i-1]]+1,a[v[i]],(mod-val)%mod);
upd(1,1,mxv,1,a[v[i-1]],(mod-val)%mod);
}else{
mdf(1,1,mxv,a[v[i]]+1,a[v[i-1]]);
upd(1,1,mxv,1,a[v[i]],(mod-val)%mod);
}
tmp=-tmp;
res.push_back((tmp*ts[1].val+mod)%mod);
}
}
int result=0;
for(int i=(int)res.size()-1;i>=0;i--){
if(((int)res.size()-i)&1)result=(result+res[i])%mod;
else result=(result-res[i]+mod)%mod;
}
ans=1ll*ans*result%mod;
}
int main(){
freopen("rainbow.in","r",stdin);
freopen("rainbow.out","w",stdout);
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=0;i>a[i];
mxv=0;
for(int i=0;i>u>>v;
u--;v--;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=0;i