https://codeforces.com/problemset/problem/2144/E1
题意概述
\(n\) 座塔从左到右排列，高度为 \(a_i\)，记 \(L(a)\) 为从左看依次能看见的塔的高度，\(R(a)\) 为从右看依次能看见的塔的高度，求满足 \(L(a)=L(a')\) 且 \(R(a)=R(a')\) 的 \(a'\) 数量，其中 \(a'\) 是 \(a\) 的子序列，模 \(998244353\).
\(1\le n \le 5000\).
思路
只考虑左边，考虑 \(dp\)，记 \(dp1[i][j]\) 为 \(a\) 中前 \(i\) 个元素能匹配 \(L(a)\) 的前 \(j\) 个元素的方案数，讨论每个位置选或不选转移即可.
类似地处理右边，记为 \(dp2\).
考虑如何整合，发现只需关注最大值位置，枚举左边最大值第一次出现位置 \(p\) 和右边最大值第一次出现位置 \(q\)，将两边方案数相乘，中间数任选.
为了刻画最大值第一次出现，需要一些处理，记 \(len=|idx|\)，\(m_1=|L(a)|\)，\(m_2=|R(a)|\)， 具体地，总贡献为：
\[\sum_{i=0}^{len}{\sum_{j=i}^{len}{dp1[idx[i]-1][m_1-1] \cdot dp2[idx[j]+1][m_2-1] \cdot 2^{\max(0,idx[j]-idx[i]-1)}}}
\]
时间复杂度 \(\mathcal{O}(n^2)\).
代码
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int MOD = 998244353;
const int INF = 1e9;ll qpow(ll a,ll b){ll res = 1;while (b){if (b&1){res = res*a%MOD;}a = a*a%MOD;b >>= 1;}return res;
}void solve(){int n;cin >> n;vector<int> a(n+1);for (int i=1;i<=n;i++){cin >> a[i];}int pre = 0;vector<int> temp{0};for (int i=1;i<=n;i++){pre = max(pre,a[i]);temp.push_back(pre);}sort(temp.begin()+1,temp.end());temp.erase(unique(temp.begin()+1,temp.end()),temp.end());int m = temp.size()-1;vector<vector<ll>> dp(n+1,vector<ll>(m+1));dp[0][0] = 1;for (int i=1;i<=n;i++){dp[i] = dp[i-1];for (int j=0;j<=m;j++){if (a[i]<=temp[j]){dp[i][j] = (dp[i][j]+dp[i-1][j])%MOD;}else if (j+1<=m && a[i]==temp[j+1]){dp[i][j+1] = (dp[i][j+1]+dp[i-1][j])%MOD;}}} int suf = 0;temp.clear();temp.push_back(0);for (int i=n;i>=1;i--){suf = max(suf,a[i]);temp.push_back(suf);}sort(temp.begin()+1,temp.end());temp.erase(unique(temp.begin()+1,temp.end()),temp.end());int m2 = temp.size()-1;vector<vector<ll>> dp2(n+2,vector<ll>(m2+1));dp2[n+1][0] = 1;for (int i=n;i>=1;i--){dp2[i] = dp2[i+1];for (int j=0;j<=m2;j++){if (a[i]<=temp[j]){dp2[i][j] = (dp2[i][j]+dp2[i+1][j])%MOD;}else if (j+1<=m2 && a[i]==temp[j+1]){dp2[i][j+1] = (dp2[i][j+1]+dp2[i+1][j])%MOD;}}}int mx = temp.back();vector<int> idx;for (int i=1;i<=n;i++){if (a[i]==mx){idx.push_back(i);}}int len = idx.size();ll res = 0;for (int i=0;i<len;i++){for (int j=i;j<len;j++){res = (res+dp[idx[i]-1][m-1]*dp2[idx[j]+1][m2-1]%MOD*qpow(2,max(0,idx[j]-idx[i]-1))%MOD)%MOD;}}cout << res << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}