Beautiful Sqeuence

题目描述

题目链接

给定一个整数数组a，其中每个元素都是1到3之间的值。美丽序列定义如下：
– 序列长度至少为3。
– 对于除第一个元素之外的每个元素，左侧存在一个比它小的元素。
– 对于除最后一个元素之外的每个元素，右侧存在一个比它大的元素。
任务是计算数组a中美丽子序列的数量，并由于答案可能非常大，输出结果需要对998244353取模。

题解

DP处理：
– 遇到1时增加1结尾的子序列计数
– 遇到2时基于现有的1结尾子序列扩展出新的2结尾序列
– 遇到3时基于现有的2结尾子序列计算出子序列数量。

时间复杂度O(n)。

完整代码

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

#define ll long long
#define akitama return 0
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define fast_io cin.tie(nullptr)->ios::sync_with_stdio(false)
#define endl '\n'

const int MOD = 998244353;
/*
    AKITAMA CODEFORCES EDU174 C SOLUTION 25.2.18 
    TARGET: up to C++23 
*/

void solve() {
    int n;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
    }

    ll f1 = 0, f2 = 0, ans = 0;
    for (int i = 0; i < n; i ++) {
        if (a[i] == 1) {
            f1 = (f1 + 1) % MOD;
        } else if (a[i] == 2) {
            f2 = (f2 * 2 + f1) % MOD;
        } else if (a[i] == 3) {
            ans = (ans + f2) % MOD;
        }
    }
    cout << ans << endl;
}

signed main() {
    fast_io;
    int _;
    cin >> _;
    while (_) {
        solve();_--;
    }
    akitama;
}