2026天梯赛选拔赛-L1-7-简单计数（赛时-号搞错成加号了，绷不住了） · znzryb
## 题目大意
给定 $n$ 个人从左到右站成一排。每个人的身份只有两种：诚实者或欺诈者。
- 诚实者一定说真话。
- 欺诈者可能说真话，也可能说假话。
- 第 $i$ 个人会报一个数 $a_i$，表示“自己左边有多少个欺诈者”。
- 额外保证：不存在两个相邻的欺诈者。
任务是统计：一共有多少种身份安排（每个人是诚实者或欺诈者）能够与所有人的发言同时不矛盾。结果对 `998244353` 取模输出。
输入为两行：
- 第一行是 $n$。
- 第二行是 $n$ 个整数 $a_i$。
输出为一行：满足条件的方案数（取模后）。
样例：
```
输入：
6
0 0 0 0 0 0
输出：
2
```
样例含义：6 个人都说自己左边有 0 个欺诈者。在“欺诈者不相邻”的前提下，能成立的身份安排共有 2 种。
## 思路讲解
```cpp
// 0 shuo huang
for(int i=1;i<=N;++i){
if(i==1){
if(A[i]==0){
dp[i][1]=1;
dp[i][0]=1;
}else{
dp[i][0]=1;
}
continue;
}
// 说谎者只能从前面一个的诚实者转移过来
// 因为不能连续两个都是说谎者
dp[i][0]=dp[i-1][1];
if(A[i]==A[i-1]){
// 可以从诚实者转移过来的条件
dp[i][1]+=dp[i-1][1];
dp[i][1]%=mod;
}
if(A[i]==A[i-2]+1){
// 可以从说谎者转移过来的条件
// 之所以是这个，是因为如果前面一个是说谎者的话，那么再前面一个就是诚实者
dp[i][1]+=dp[i-1][0];
dp[i][1]%=mod;
}
}
```
## AC代码
AC
[http://10.199.227.101/contest/1005/problem/L1-7/submission-detail/2146](http://10.199.227.101/contest/1005/problem/L1-7/submission-detail/2146)
::: 源代码
```cpp
#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":["<<x<<"]\n";
#define SZ(x) ((ll)x.size())
#define all(x) x.begin(),x.end()
using namespace std;
using ll = long long;
using DB = double;
const DB pi = acos(-1.0);
const ll mod = 998244353;
const ll INF = (1ll<<61)-1;
ll lT;
void Solve(){
ll N;
cin>>N;
vector<ll> A(N+2);
for(int i=1;i<=N;++i){
cin>>A[i];
}
vector<array<ll,2>> dp(N+2);
// 0 shu huang
for(int i=1;i<=N;++i){
if(i==1){
if(A[i]==0){
dp[i][1]=1;
dp[i][0]=1;
}else{
dp[i][0]=1;
}
continue;
}
dp[i][0]=dp[i-1][1];
if(A[i]==A[i-1]){
dp[i][1]+=dp[i-1][1];
dp[i][1]%=mod;
}
if(A[i]==A[i-2]+1){
dp[i][1]+=dp[i-1][0];
dp[i][1]%=mod;
}
}
ll ans=dp[N][0]+dp[N][1];
ans%=mod;
cout<<ans<<"\n";
// mod
}
int main(){
cin.tie(0)->sync_with_stdio(false);
// cin>>lT;
// while(lT--)
Solve();
}
/*
*/
```
:::
## 心路历程（WA，TLE，MLE……）