题解：CF2069C Beautiful Sequence
xAlec
·
·
题解
CF2069C
Statement
我们定义一个序列为美丽的当它满足：
- 序列长度至少为 3。
- 除第一个元素外，每个元素左侧都有一个小于它的元素。
- 除最后一个元素外，每个元素右侧都有一个大于它的元素。
给定长度 n 的数组 a，求 a 的所有子序列中美丽的子序列的个数，答案对 998244353 取模。
## Solution
我们拥有人类智慧。
看到 $a_i \in [1,3]$ 我们试试考虑算贡献，记产生正贡献 / 负贡献分别为 $G,F$。
$1$ 开头 $3$ 结尾中间全是 $2$ 的子序列满足条件。
- 对于 $a_i = 2$，它对于左右两边的 $1,3$ 均有贡献，可以插在中间，所以更新 $G \leftarrow G \times 2$。
- 对于 $a_i = 3$，它对于左边的 $1,2$ 有贡献，但是右边毫无贡献，只能作为末尾，更新 $G \leftarrow G + 1,F \leftarrow F + 1$。
- 对于 $a_i = 1$，同理只能作为开头，这时更新答案 $ans \leftarrow ans + G - F$。
## Code
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 33, MOD = 998244353;
int T, n, A[MAXN];
signed main() {
scanf ("%lld", &T);
while (T --) {
scanf ("%lld", &n);
for (int i = 1; i <= n; i ++)
scanf ("%lld", &A[i]);
int F = 0, G = 0, Ans = 0;
for (int i = n; i; i --) {
if (A[i] == 2) {
G = (G << 1) % MOD;
} else if (A[i] == 3) {
F ++, G ++;
} else {
Ans = (Ans + G - F + MOD) % MOD;
}
}
printf ("%lld\n", Ans);
}
return 0;
}
```