本文共 1343 字，大约阅读时间需要 4 分钟。

题意：

n个正整数组成一个a序列，求满足要求的b序列的种类数。a,b序列下标从1开始。b序列满足：

1.b1 = 0。

2.当ai = aj时，bi = bj。

3.bi = b(i+1) 或bi + 1 = b(i + 1)。

题解：

1.以1 2 1 2 3举例：第1个数与第3个数一样，因为b是一个不减序列，所以区间[1,3]的数字必须相同。又因为第2个数和第4个数相同，那么区间[2,4]的数字必须相同，因为[1,3]和[2,4]有交集，那么[1,4]的数字必须相同。第5个数字只与自己相同，故[5,5]区间的数字相同。因此划分出了2个区间。因为b1 = 0，那么第1个区间为0。因为b序列的不减特性，第2个区间可以与第1个区间数字相同，也可以比第1个区间数字大1。故答案是2 ^ (区间数 - 1)。

2.如果暴力划分区间的话会超时，提前排序会减低复杂度。

#include<bits/stdc++.h>#define N 200005#define mod 998244353using namespace std ;struct Node{  int id ;  int num ;	} a[N] ;int pre[N] ;long long pow1(int x , int y){	int i ;	long long ans = 1 ;    for(i = 1 ; i <= y ; i ++)       ans = (ans * x) % mod ;    return ans ;}bool cmp(Node x , Node y){	if(x.num != y.num)	   return x.num < y.num ;	return x.id < y.id ;}int main(){  int n ;  int i , j , k ;	  int temp1 , temp2 ;  int cnt = 0 ;  long long ans ;  scanf("%d" , &n) ;  for(i = 1 ; i <= n ; i ++)  {  	 pre[i] = i ;  	 a[i].id = i ;     scanf("%d" , &a[i].num) ;  }  sort(a + 1 , a + n + 1 , cmp) ;  for(i = 1 ; i <= n ; i ++)  {  	 j = i ;  	 while(j + 1 <= n && a[j + 1].num == a[i].num)         j ++ ;     pre[a[j].id] = a[i].id ;     i = j ;  }  for(i = n ; i >= 1 ; i --)  {  	 temp1 = pre[i] ;  	 cnt ++ ;  	 for(j = i ; j >= temp1 ; j --)  	    temp1 = min(temp1 , pre[j]) ;	     i = temp1 ;  }  ans = pow1(2 , cnt - 1) ;  printf("%lld" , ans) ;}