Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Every valid subsequence must contain at least one occurrence of the global maximum. That height is visible from both sides in the original, so skipping all of it is instantly dead.
Split a chosen subsequence by its first selected global maximum and its last selected global maximum. Anything between them is invisible from both sides, because the maximum is already blocking both views.
So the problem becomes: count valid left prefixes before the first selected maximum, count valid right suffixes after the last selected maximum, and multiply by for the totally free middle.
For the left prefix, forget the right view completely. You only need subsequences whose record-high sequence is exactly without the global maximum. This is a small DP over how many required record heights have already appeared.
When processing a value in that DP: you may skip it; you may take it without changing state if it is at most the current record; and you may advance exactly one state if equals the next required record. Any other selected value would create a bogus visible height, which is how the whole thing goes off the rails.
Let be the maximum value in the array.
A small but important point: although the statement talks about sets and , visible heights are always strictly increasing as you scan from one side. So once we know the set, the visible order is forced by height. We can safely treat the target visible heights as an increasing sequence.
The global maximum is visible from both sides in the original array. Therefore every valid subsequence must select at least one occurrence of .
Now take any valid subsequence and define:
Then and .
This split is the whole trick.
So for fixed , the middle is completely free. If , there are indices between them, giving choices. If , there is no middle factor.
Now we only need two arrays:
Then the answer is:
No double counting: every valid subsequence has exactly one first selected maximum and one last selected maximum.
Left DP
Let the required left-visible heights before be:
These are exactly the prefix maxima of the original array, excluding .
Scan the array from left to right. Define:
Initially .
For a value :
Before processing index , the value is the number of valid left parts ending before , so if , we store it as .
Right DP
Same thing, but scan from right to left. The target sequence is made from suffix maxima of the original array, excluding .
This gives for every maximum position .
Complexity
Each DP is in the worst case, and the final summation over maximum positions is also . With , this is comfortably fine.
Memory usage is .
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
vector<ll> countLeft(const vector<ll>& a, const vector<ll>& target, ll H) {
int n = (int)a.size();
int k = (int)target.size();
vector<ll> dp(k + 1), res(n);
dp[0] = 1;
for (int i = 0; i < n; i++) {
res[i] = dp[k];
if (a[i] == H) continue;
vector<ll> ndp = dp;
for (int j = 0; j <= k; j++) {
if (!dp[j]) continue;
if (j > 0 && a[i] <= target[j - 1]) {
ndp[j] += dp[j];
if (ndp[j] >= MOD) ndp[j] -= MOD;
}
if (j < k && a[i] == target[j]) {
ndp[j + 1] += dp[j];
if (ndp[j + 1] >= MOD) ndp[j + 1] -= MOD;
}
}
dp.swap(ndp);
}
return res;
}
vector<ll> countRight(const vector<ll>& a, const vector<ll>& target, ll H) {
int n = (int)a.size();
int k = (int)target.size();
vector<ll> dp(k + 1), res(n);
dp[0] = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] = dp[k];
if (a[i] == H) continue;
vector<ll> ndp = dp;
for (int j = 0; j <= k; j++) {
if (!dp[j]) continue;
if (j > 0 && a[i] <= target[j - 1]) {
ndp[j] += dp[j];
if (ndp[j] >= MOD) ndp[j] -= MOD;
}
if (j < k && a[i] == target[j]) {
ndp[j + 1] += dp[j];
if (ndp[j + 1] >= MOD) ndp[j + 1] -= MOD;
}
}
dp.swap(ndp);
}
return res;
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<ll> a(n);
for (ll &x : a) cin >> x;
ll H = *max_element(a.begin(), a.end());
vector<ll> leftTarget;
ll cur = 0;
for (ll x : a) {
if (x > cur) {
cur = x;
if (x != H) leftTarget.push_back(x);
}
}
vector<ll> rightTarget;
cur = 0;
for (int i = n - 1; i >= 0; i--) {
if (a[i] > cur) {
cur = a[i];
if (a[i] != H) rightTarget.push_back(a[i]);
}
}
vector<ll> left = countLeft(a, leftTarget, H);
vector<ll> right = countRight(a, rightTarget, H);
vector<ll> pow2(n + 1, 1);
for (int i = 1; i <= n; i++) pow2[i] = pow2[i - 1] * 2 % MOD;
vector<int> mx;
for (int i = 0; i < n; i++) {
if (a[i] == H) mx.push_back(i);
}
ll ans = 0;
for (int p : mx) {
for (int q : mx) {
if (q < p) continue;
ll ways = left[p] * right[q] % MOD;
if (p < q) ways = ways * pow2[q - p - 1] % MOD;
ans += ways;
if (ans >= MOD) ans -= MOD;
}
}
cout << ans << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
vector<ll> countLeft(const vector<ll>& a, const vector<ll>& target, ll H) {
int n = (int)a.size();
int k = (int)target.size();
vector<ll> dp(k + 1), res(n);
dp[0] = 1;
for (int i = 0; i < n; i++) {
res[i] = dp[k];
if (a[i] == H) continue;
vector<ll> ndp = dp;
for (int j = 0; j <= k; j++) {
if (!dp[j]) continue;
if (j > 0 && a[i] <= target[j - 1]) {
ndp[j] += dp[j];
if (ndp[j] >= MOD) ndp[j] -= MOD;
}
if (j < k && a[i] == target[j]) {
ndp[j + 1] += dp[j];
if (ndp[j + 1] >= MOD) ndp[j + 1] -= MOD;
}
}
dp.swap(ndp);
}
return res;
}
vector<ll> countRight(const vector<ll>& a, const vector<ll>& target, ll H) {
int n = (int)a.size();
int k = (int)target.size();
vector<ll> dp(k + 1), res(n);
dp[0] = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] = dp[k];
if (a[i] == H) continue;
vector<ll> ndp = dp;
for (int j = 0; j <= k; j++) {
if (!dp[j]) continue;
if (j > 0 && a[i] <= target[j - 1]) {
ndp[j] += dp[j];
if (ndp[j] >= MOD) ndp[j] -= MOD;
}
if (j < k && a[i] == target[j]) {
ndp[j + 1] += dp[j];
if (ndp[j + 1] >= MOD) ndp[j + 1] -= MOD;
}
}
dp.swap(ndp);
}
return res;
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<ll> a(n);
for (ll &x : a) cin >> x;
ll H = *max_element(a.begin(), a.end());
vector<ll> leftTarget;
ll cur = 0;
for (ll x : a) {
if (x > cur) {
cur = x;
if (x != H) leftTarget.push_back(x);
}
}
vector<ll> rightTarget;
cur = 0;
for (int i = n - 1; i >= 0; i--) {
if (a[i] > cur) {
cur = a[i];
if (a[i] != H) rightTarget.push_back(a[i]);
}
}
vector<ll> left = countLeft(a, leftTarget, H);
vector<ll> right = countRight(a, rightTarget, H);
vector<ll> pow2(n + 1, 1);
for (int i = 1; i <= n; i++) pow2[i] = pow2[i - 1] * 2 % MOD;
vector<int> mx;
for (int i = 0; i < n; i++) {
if (a[i] == H) mx.push_back(i);
}
ll ans = 0;
for (int p : mx) {
for (int q : mx) {
if (q < p) continue;
ll ways = left[p] * right[q] % MOD;
if (p < q) ways = ways * pow2[q - p - 1] % MOD;
ans += ways;
if (ans >= MOD) ans -= MOD;
}
}
cout << ans << '\n';
}
}