这题的代码很短，但是建模很有思维含量，好题，记录一下
题意:
给定n,q，表示一个数组长度为n(初始下标从1开始),初始时全为0
总共有q种操作，每个操作给定一个区间[l,r]
表示可以将这个区间[l,r]取反
问:经过若干次上述q种操作后，可以得到多少不同的序列，答案对998244353取模
link: https://www.codechef.com/problems-old/CRINGEQUERY
题解
我们考虑建立一个\(b\)数组，\(b[i]\)=\(a[i]\)^\(a[i+1]\)，长度为\(n+1\)，下标范围\([0,n]\)
但是为什么是异或呢?大概是这样可以表示区间端点?
对于每一个操作\([l,r]\)，\(b[l-1]\)和\(b[r]\)显然会发生变化，因为更改了\(b[l]\)和\(b[r]\)的值
于是我们可以在\(l-1\)和\(r\)之间连一条边，建一张无向图
一张图中可能有多个部分，对于每个部分，我们计算它的 边数\(siz\)，它的贡献方案为 \(2^{siz-1}\)
由于每个部分互不联通，每个块贡献分开，于是分别计算它们的\(siz\)，贡献方案为 \(2^{siz-1}\)
最后每个块的贡献相乘就是得到的不同序列的方案数
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
const int mod=998244353;
int read() {
int x=0,f=1;
char ch=getchar();
while(ch<48||ch>57) {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>=48&&ch<=57) {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
int n,q;
int vis[N],siz=0;
vector<int> p[N];
int mul(int x,int y) {
return x*y%mod;
}
int ksm(int a,int b) {
int ans=1;
while(b) {
if(b&1) ans*=a,ans%=mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
void dfs(int x) {
if(vis[x]) return ;
vis[x]=1;
siz++;
for(int i=0;i<p[x].size();i++) {
int y=p[x][i];
dfs(y);
}
}
signed main() {
n=read();
q=read();
while(q--) {
int l=read(),r=read();
p[l-1].push_back(r);
p[r].push_back(l-1);
}
int ans=1;
for(int i=0;i<=n;i++) {
if(vis[i]) continue;
siz=0;
dfs(i);
ans=mul(ans,ksm(2,siz-1));
}
printf("%lld\n",ans);
return 0;
}