题解：CF2069C Beautiful Sequence

· · 题解

题意

定义一个“美丽”的序列为：除第 1 个数，每个数左边都有至少 1 个比它小，除最后一个数，每个数右边都有至少 1 个比它大。给定一个只由 \{1,2,3\} 组成的数组，求有多少个“美丽”的子序列。

题解

我们看到只会有 \{1,2,3\} 出现，想到从这里入手。因为在数组里不会有比 1 更小的数，所以 1 只会是子序列的左端点。同理可得 3 只会是子序列的右端点。而它们俩中间夹的 2 会和它们组成一个合法子序列。如果一对 1 和 3 中间夹了 k 个 2，那么合法的子串数量就是 2^k - 1。现在我们就有 O(n^2) 做法：循环每个 1，对于每个 1 循环找到它后面的每个 3 并统计 1 和这个 3 之间夹了多少个 2，然后统计答案。

我们还得想如何把它变成 O(n) 或者 O(n \log n) 的做法。我们掏一个样例：1 2 3 2 1 3 2 2 3。对于每个 1，我们把它对于答案的贡献写出来。

\begin{aligned} \text{第一个 1} \quad & 2^1 + 2^2 + 2^4 - 3 \\ \text{第二个 1} \quad & 2^0 + 2^2 - 2 \\ \end{aligned}

现在我们需要人类智慧。我们发现后面减的数就是这个 1 后面 3 的个数。再把后面减掉的数先扔掉，发现就是一堆 2^k 相加。结合样例分析：每个 3 会使贡献的项数增加 1，每个 2 会使贡献乘 2。那么我们从后往前循环，记录 cnt 表示出现了多少个 3，now 表示现在如果出现一个 1 需要计算答案，它贡献的 2^k 部分是多少。那么我们按照如下过程模拟：

这样我们就成功的搞出了一个 O(n) 的人类智慧解法。

代码

#include<bits/extc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int n;
void solve()
{
    cin >> n;
    vector<int>a(n + 5);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int cnt = 0,ans = 0,now = 0;
    for (int i = n; i >= 1; i--)
    {//从后往前循环，模拟即可
        if (a[i] == 3)
        {
            cnt++;
            now++;
        }
        else if (a[i] == 1)
            ans = (ans + now - cnt + mod) % mod;
        else
            now = (now << 1) % mod;
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}