题目链接
题目解法
首先第二个条件等价于同一种权值红蓝交错填
可得不考虑第三个条件的方案数为 \(2^{cntcol}\)，其中 \(cntcol\) 为出现过的颜色数量
考虑红蓝是等价的，所以 \(p>q\) 的方案数 \(=\) \(p<q\) 的方案数
所以我们只需要计算 \(p=q\) 的方案数即可算出答案
我们考虑将颜色相同的相邻的两个位置抽象成一条线段
那么不合法当且仅当线段之间存在包含关系，这个结论是好得出的
对于合法的情况，我们考虑将颜色一定需要相同位置之间连边，然后就相当于等价类个数统计，一遍 \(dfs\) 即可
时间复杂度 \(O(n\log n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
#define l first
#define r second
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int P=998244353,iv2=499122177;
const int N=200100,V=200000;
int n,a[N];
bool vis[N];
vector<int> col[N];
pii range[N];
vector<int> G[N];
void dfs(int u){
vis[u]=1;
for(int v:G[u]) if(!vis[v]) dfs(v);
}
int main(){
n=read();
F(i,1,n) a[i]=read();
F(i,1,n) col[a[i]].pb(i);
int tot=1;
F(i,1,V) if(!col[i].empty()) tot=tot*2%P;
bool flg=1;
F(i,1,V) if(col[i].size()&1){ flg=0;break;}
if(flg){
int cnt=0;
F(i,1,V) for(int j=0;j<col[i].size();j+=2) range[++cnt]={col[i][j],col[i][j+1]};
sort(range+1,range+cnt+1);
int mx=0;
F(i,1,cnt){
if(mx>range[i].r){ flg=0;break;}
chkmax(mx,range[i].r);
}
if(flg){
F(i,1,V) F(j,0,SZ(col[i])-2) G[col[i][j]].pb(col[i][j+2]),G[col[i][j+2]].pb(col[i][j]);
F(i,1,cnt-1)
if(range[i].r>range[i+1].l){
G[range[i].l].pb(range[i+1].l),G[range[i+1].l].pb(range[i].l);
G[range[i].r].pb(range[i+1].r),G[range[i+1].r].pb(range[i].r);
}
int res=0;
F(i,1,n) if(!vis[i]) dfs(i),res++;
res/=2;
int bs=1;
while(res--) bs=bs*2%P;
tot=(tot-bs+P)%P;
}
}
printf("%d\n",1ll*tot*iv2%P);
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}