Beautiful Sequence

Problem Statement

Let’s call an integer sequence beautiful if the following conditions hold:

its length is at least $3$;
for every element except the first one, there is an element to the left less than it;
for every element except the last one, there is an element to the right larger than it;

For example, $[1, 4, 2, 4, 7]$ and $[1, 2, 4, 8]$ are beautiful, but $[1, 2]$, $[2, 2, 4]$, and $[1, 3, 5, 3]$ are not.

Recall that a subsequence is a sequence that can be obtained from another sequence by removing some elements without changing the order of the remaining elements.

You are given an integer array $a$ of size $n$, where every element is from $1$ to $3$. Your task is to calculate the number of beautiful subsequences of the array $a$. Since the answer might be large, print it modulo $998244353$.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 3$).

Additional constraint on the input: the sum of $n$ over all test cases doesn’t exceed $2 \cdot 10^5$.

Output

For each test case, print a single integer — the number of beautiful subsequences of the array $a$, taken modulo $998244353$.

Sample Input

1
2
3
4
5
6
7
8
9


4
7
3 2 1 2 2 1 3
4
3 1 2 2
3
1 2 3
9
1 2 3 2 1 3 2 2 3

Sample Output

Explanation of example

In the first test case of the example, the following subsequences are beautiful:

$[a_3, a_4, a_7]$;
$[a_3, a_5, a_7]$;
$[a_3, a_4, a_5, a_7]$.

Solving

简易分析一下题目就可以得出，题目是让我们求样式为[1,2,…,3]的序列数量，这个序列必须以1开头，3结尾，中间至少有一个2。

根据简单的数学我们可以得知，若一个序列中，中间2的个数为K。

我们对每个其中的2，分为选和不选两种情况，则K个2就会有$2^{k}$种情况，再排除一个所有都不选的情况。

则这个以1开头，3结尾的合法序列个数会是 $2^{k}$-1;

根据这个结论，我们可以建立两个数组pre2[N],suf3[N]分别代表：

第i个元素前有多少个2和第i个元素后有多少个3。

为了方便计算$2^{k}$，我们在计算开始前，先提前预处理一下$2^{k}$和$2^{-k}$（即$2^{k}$的逆元）

这样我们可以再维护一个数组val3[N]，它表示了当前元素位置后所有3的贡献总和，要想得到答案，我们只需要每当遍历到一个1时，取

后面所有3的总贡献val3[i] * $2^{-pre2[i]}$-后面三的数量cnt3[i]

其中val3[i]代表：

$$ \sum_{arr[i]=3}2^{pre2[i]} $$

即对于当前1后面所有3的总贡献，但这些贡献在算取的时候都是按当前3之前所有的2的个数来算取的，所以我们要依次在指数上减去算多的部分，答案即为:

$$ \sum_{j: arr[j]=1}\left(\left(\sum_{i > j, arr[i]=3}2^{pre2[i]}\right)\times2^{-pre2[j - 1]}-cnt3[j]\right) $$

其中指数相减的部分我们可以每当遍历到1时，给它当前位置后的3的总贡献与$2^{pre2[i]}$的逆元相乘得出。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92


#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f
#define NINF -0x3f3f3f3f
//#define Single
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 2e5+10;
const int M = 0;
const int MOD = 998244353;
int pow_2[N],invpow_2[N];
//预处理2的幂和2的幂的逆元
void pre()
{
    pow_2[0] = 1;
    invpow_2[0] = 1;
    for(int i=1;i<N;i++)
    {
        pow_2[i] = (pow_2[i-1] * 2LL)%MOD;//2在模意义下的幂
    }
    int inv2 = (MOD+1)/2;//2在模意义下的逆元
    for(int i=1;i<N;i++)
    {
        invpow_2[i] = (invpow_2[i-1] * inv2 * 1LL)%MOD;
    }
}
void solve()
{
    int n;
    cin >> n;
    int arr[n+1];
    for(int i=1;i<=n;i++) cin >> arr[i];
    int pre2[n+2],val3[n+2],suf3[n+2];
    // pre2[i] 表示第 i 个元素前 2 的数量
    pre2[0] = 0;
    for(int i=1;i<=n;i++)
    {
        pre2[i] = pre2[i-1];
        pre2[i] += (arr[i]==2);
    }
    // suf3[i] 表示第 i 个元素后 3 的数量
    suf3[n+1] = 0;
    for(int i=n;i>=1;i--)
    {
        suf3[i] = suf3[i+1];
        suf3[i] += (arr[i]==3);
    }
    // val3[i] 表示第 i 个元素后所有 3 的贡献总和
    //总共可能性2^k;
    val3[n+1] = 0;
    for(int i=n;i>=1;i--)
    {   
        val3[i] = val3[i+1];
        if(arr[i]==3)
        {
            int k = pre2[i];
            val3[i] = (val3[i]+pow_2[k]*1LL)%MOD;
        }
    }
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        if(arr[i]==1)
        {
           	int k = pre2[i - 1]; // 当前 1 元素之前 2 的数量
            int val = val3[i]; // 当前 1 元素后所有 3 的贡献总和
            int cnt = suf3[i]; // 当前 1 元素后 3 的数量
            int res = (1LL*val*invpow_2[k]-cnt + MOD)%MOD;
            ans = (ans + res) % MOD;
        }
    }
    cout << ans%MOD << endl;
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T;
#ifdef Single
    T = 1;
#else
    cin >> T;
#endif
    pre();
    while(T--)
    {
        solve();
    }
    return 0;
}