Value series solution report

label ： extremum Combinatorial number

Topic link

source ： Cattle from

Their thinking ：

According to the topic definition , It is deduced that the value of a monotonic sequence is the absolute value of the difference between the first two ends , Then try to find the extreme point of the sequence first
To facilitate data processing, we use two arrays to count ,
a The array is included in the array after weight removal （ In this way, it is convenient to judge whether it is the extreme point ）
b The array counts the number of original numbers
such as 1 3 3 4 4
Array a The values of are 1 3 4
Array b The values of are 1 2 2
Then consider the influence of extreme number and non extreme number on the final answer
For continuous same extremum （ Aforementioned a[3]） We must keep at least one ans * = 2 Of a[3] Time -1
All non extreme points can be retained or not ans * = 2*2
We use fast exponents to reduce complexity

Code implementation ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 8;
int a[N],c[N];
ll ksm(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) (ans *= a) %= mod;
		(a *= a) %= mod;
		b >>= 1;
	}
	return ans;
}

bool check(int i){
	return (a[i] > a[i - 1] && a[i] > a[i + 1]) || (a[i] < a[i - 1] && a[i] < a[i + 1]);
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		ll n;
		ll ans = 1;
		cin >> n;
		int na=0,x;
		memset(a,0,sizeof(a));
		memset(c,0,sizeof(c));
		for (int i = 1; i <= n; i++) {
			scanf("%d", &x);
			if(a[na]==x){
			   c[na]++;
			}
			else{
				na++;
				a[na]=x;
				c[na]++;
			}
					
		}
        
		int cnt=n;
		if(na==1){
			(ans *= ksm(2, c[1])-1) %= mod;
			cout<<ans<<endl;
			continue;
		}
		else{
			(ans *= ksm(2, c[1])-1) %= mod;
			(ans *= ksm(2, c[na])-1) %= mod;
			cnt -= c[1]+c[na];
		}
		
		for (int i = 2; i <= na-1; i++) {
			if (check(i)) {
			    cnt -= c[i];
				(ans *= ksm(2, c[i])-1) %= mod;	
			}
		}	

		(ans *= ksm(2, cnt)) %= mod;
		cout << ans << endl;
	}
	return 0;
}