思路

扫描序列并增量维护三个计数：

• c1：到当前位置为止，数字 $1$ 出现的次数；
• c12：到当前位置为止，子序列 12 的个数；
• c123：到当前位置为止，子序列 123 的个数。

遍历到每个元素时按它的值更新：

• 若为 $1$：它自己可以作为一个新的子序列开头，c1 加 $1$；
• 若为 $2$：此前每一个 $1$ 都能和这个 $2$ 拼成 12，c12 加上 c1；
• 若为 $3$：此前每一个 12 都能和这个 $3$ 拼成 123，c123 加上 c12。

由于每次都是"当前元素接在已有子序列后面"，同一位置的元素不会重复使用，计数恰好等于所有 123 子序列的个数。答案可能较大，全程使用 long long。

时间复杂度 $O(n)$，空间复杂度 $O(n)$（存原数组，实际可以边读边算做到 $O(1)$ 额外空间）。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

// 单组数据：统计序列中 "123" 子序列的个数
void go(){
    int n; cin >> n;
    vector<int> a(n + 1, 0);
    for(int i = 1; i <= n; i++) cin >> a[i];

    // c1  : 已出现的 1 的个数
    // c12 : 已能组成的 "12" 子序列个数
    // c123: 已能组成的 "123" 子序列个数
    int c1 = 0, c12 = 0, c123 = 0;

    for(int i = 1; i <= n; i++){
        if(a[i] == 1){
            c1++;              // 这个 1 可以作为新子序列的开头
        }else if(a[i] == 2){
            c12 += c1;         // 每个已有的 1 都能和当前 2 配成 "12"
        }else if(a[i] == 3){
            c123 += c12;       // 每个已有的 "12" 都能和当前 3 配成 "123"
        }
    }

    cout << c123 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int _ = 1;
    // 本题只有一组数据，不需要读入测试组数
    while(_--){
        go();
    }
    return 0;
}