链接 :
Problem - E - Codeforces
思路 :
区间合并 + 快速幂
对于a[0],那么从第一个a[0],到最后一个a[0]这个区间内所有b值全部为b[0] = 0,以此类推,对于其他值也是一样;
例如对于[1 , 2 , 1 , 2 , 3]
首先b[0] = 0(题目要求) , 然后因为a[2] = a[0] ,那么b[2]=b[0] = 0;
要求bi+1=bi 或 b[i+1]=b[i]+1 , 那么b[1]夹在两个0之间,只能为0 , 同理b[3] = b[1] = 0 ;
对于b[4] = b[3] = 0 , 或b[4] = b[3] + 1 ;
依此 : 我们要求一个区间数量,每两个区间要满足无相同值,这里先求出每个值出现的范围,然后左端点排序,然后进行合并 , 得到区间数量t;
然后ans 等于2的(t-1)次方(由于b[0]已经固定为1,后面一个区间可以取上一个区间+0/+1的值)
代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define int long long
typedef long long LL;
const LL mod = 998244353;
const int N = 2e5+10;
typedef pair<int, int> PII;
LL qmi(LL m, LL k,LL p){
LL res = 1 % p, t = m;
while (k){
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res%p;
}
void merge(vector<PII> &segs){
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
inline void solve(){
// 详细地址 : https://codeforces.com/contest/1102/submission/259938745
int n ; cin >> n ;
vector<int> a(n+1) ; vector<PII> b; set<int> st ; map<int,vector<int>> mp ;
for(int i=1;i<=n;i++) cin >> a[i] ,mp[a[i]].push_back(i) ;
for(int i=1;i<=n;i++){
if(st.count(a[i])) continue ;
b.push_back({i,mp[a[i]].back()}) ;
st.insert(a[i]) ;
}
merge(b) ;//区间合并
int t = b.size() - 1 ;
LL ans = qmi(2,t,mod) ;//快速幂
cout << ans << endl ;
}
signed main(){
IOS
int _ = 1;
while(_ --) solve();
return 0;
}