题目描述

难度分:$1900$

输入$T(\leq 10^5)$表示$T$组数据。所有数据的$n$之和$\leq 5 \times 10^5$。

每组数据输入$n(1 \leq n \leq 5 \times 10^5)$和长为$n$的数组$a(0 \leq a[i] \leq n)$。

称序列$b$为MEX序列，如果对所有$i$都有$|b[i] - mex(b[0],…,b[i])| \leq 1$成立，其中$mex(S)$表示不在$S$中的最小非负整数。

输出$a$的非空MEX子序列的个数，模$998244353$。

两个子序列只要有元素下标不同，就算不同的子序列。例如$a=[0,0,0]$有$7$个不同的非空子序列。

注：子序列不要求连续。

输入样例

4
3
0 2 1
2
1 0
5
0 0 0 0 0
4
0 1 2 3

输出样例

4
2
31
7

算法

动态规划

状态定义

$dp[i][j][0]$表示考虑到$a[i]$，MEX$=j$且序列中没有$j+1$的方案数。$dp[i][j][1]$表示考虑到$a[i]$，MEX$=j$且序列中有$j+1$的方案数。

状态转移

假设$a[i]=j$，首先可以确定的是：所有$dp[i][j][0]$都可以由$dp[i-1][j][0]$转移过来；所有$dp[i][j][1]$都可以由$dp[i-1][j][1]$转移过来，即不选择$j$这个数加入子序列。状态转移方程为$dp[i][j][0]=dp[i-1][j][0]$，$dp[i][j][0]=dp[i-1][j][0]$。

如果选$a[j]=j$这个数加入子序列：

1. $dp[i][j+1][0]$可以由$dp[i-1][j][0]$转移过来，即一个MEX$=j$的子序列加入$j$后MEX$=j+1$。还可以从$dp[i-1][j+1][0]$转移过来，即一个MEX$=j+1$的子序列加入$j$后没有任何改变。还可以由$dp[i][j+1][0]$转移过来，即一个MEX$=j+1$且不存在$j+2$的子序列加入$j$后，仍然满足MEX$=j+1$（加不加$j$没有影响）。
2. $dp[i][j+1][1]$可以由$dp[i-1][j+1][1]$转移过来，即一个MEX$=j+1$且存在$j+2$的子序列加入$j$后，仍然满足MEX$=j+1$。
3. $dp[i][j-1][1]$可以由$dp[i-1][j-1][1]$转移过来，即一个MEX=$j-1$，且存在$j$的子序列加入$j$后也不会有什么改变，仍然满足MEX$=j-1$。还可以由$dp[i-1][j-1][0]$转移过来，即一个MEX$=j-1$，且不存在$j$的子序列加入$j$后仍然满足MEX$=j-1$。

因此综合以上两种情况，状态转移方程为

$dp[i][j+1][0]=dp[i-1][j+1][0]+dp[i-1][j][0]+dp[i-1][j+1][0]$
$dp[i][j+1][1]=dp[i-1][j+1][1]+dp[i-1][j+1][1]$
$dp[i][j-1][0]=dp[i-1][j-1][0]$
$dp[i][j-1][1]=dp[i][j-1][1]+dp[i][j-1][1]+dp[i][j-1][0]$

最后，发现第一维$i$是可以不要的，因此不需要三维DP，只需要保留后两维即可，空间是$O(n)$的。

复杂度分析

时间复杂度

状态数量是$O(n)$级别，单次转移的时间复杂度为$O(1)$，因此算法整体的时间复杂度为$O(n)$。

空间复杂度

开辟了$n \times 2$的DP数组，额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 500010, MOD = 998244353;
int t, n, a[N];
LL dp[N][2];

int solve() {
    for(int i = 0; i <= n + 2; i++) {
        dp[i][0] = dp[i][1] = 0;
    }
    dp[0][0] = 1;     // base case
    for(int i = 1; i <= n; i++) {
        dp[a[i] + 1][0] = (dp[a[i] + 1][0] + dp[a[i]][0] + dp[a[i] + 1][0]) % MOD;
        dp[a[i] + 1][1] = (dp[a[i] + 1][1] + dp[a[i] + 1][1]) % MOD;
        if(a[i] >= 1) {
            dp[a[i] - 1][1] = (dp[a[i] - 1][1] + dp[a[i] - 1][1] + dp[a[i] - 1][0]) % MOD;
        }
    }
    LL ans = 0;
    for(int i = 0; i <= n + 1; i++) {
        ans = (ans + dp[i][0]) % MOD;
        ans = (ans + dp[i][1]) % MOD;
    }
    ans = (ans - 1 + MOD) % MOD;     // 减去一个空序列
    return ans;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        printf("%d\n", solve());
    }
    return 0;
}