动态规划、数学

优先考虑强限制，从相邻两人中至少有一个人纯真下手。

设计 $dp_{i,0}$ 为第 $i$ 个人不纯真，并且前 $i$ 个人的状态满足相邻两人至少有一个人纯真的方案数；设计 $dp_{i,1}$ 为第 $i$ 个人纯真，并且前 $i$ 个人同样满足条件的方案数。

状态 $dp_{i,0}$ 要求第 $i-1$ 个人必须纯真，于是有 $dp_{i,0}=dp_{i-1,1}$ 的转移。

状态 $dp_{i,1}$ 可以从 $dp_{i-1,0}$ 和 $dp_{i-1,1}$ 转移，先讨论比较容易的 $dp_{i-1,1}$ 这个来源。

由于第 $i-1$ 个人是纯真的，所以他前面有 $a_{i-1}$ 个人不纯真，同样地第 $i$ 个人前面也有 $a_{i-1}$ 个人不纯真，于是当且仅当 $a_{i} = a_{i-1}$ 时 $dp_{i-1,1}$ 能够转移到 $dp_{i,1}$。

如果第 $i-1$ 个人不纯真，那第 $i-2$ 个人一定纯真，当且仅当 $a_{i} = a_{i-2} + 1$ 时 $dp_{i-1,0}$ 能够转移到 $dp_{i,1}$。边界条件有些麻烦。

先令 $dp_{1,0} = 1$，若 $a_1 = 0$ 则令 $dp_{1,1} = 1$；否则令 $dp_{1,1} = 0$。由于 $dp_{i,1} \ (i \geq 2)$ 的一个转移依赖 $a_{i-2}$ 的值，单独考虑 $dp_{2,1}$ 的转移，如果 $a_2 = 1$ 则可以从 $dp_{1,0}$ 转移，实现中保持 $a_0 = 0$ 后不特判该情况也是正确的。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998'244'353;
Mint<mod> dp[200'005][2];
int n,a[200'005];
void solution(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[1][0]=1,dp[1][1]=(a[1]==0);
    for(int i=2;i<=n;i++){
        dp[i][0]=dp[i-1][1];
        if(a[i]==a[i-1]) dp[i][1]+=dp[i-1][1];
        if(a[i]==a[i-2]+1) dp[i][1]+=dp[i-1][0];
    }
    cout<<dp[n][0]+dp[n][1]<<'\n';
    for(int i=1;i<=n;i++) dp[i][0]=0,dp[i][1]=0;
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}