题解：CF2061C Kevin and Puzzle

· · 题解

可以发现样例解释出现红蓝双色，一眼dp。

发现题目很套路，可以设 dp_{i,0/1} 代表在前 i - 1 个人已经确定的情况下，第 i 个人说真话 （0）或者假话（1）。

可以发现，当这个人说假话的时候，前一个人一定说真话，后一个人也是，但由于递推，只考虑前，可得：

dp_{i,1} = dp_{i - 1,0}

那当这一个人说真话的时候，前一个人可能说真话也可能说假话，但是如果是说假话，大前个人一定说真话（因为相邻两个人不同时说假话），可得：

dp_{i,0} = \begin{cases} dp_{i - 1,0} & \text{if } a_i = a_{i - 1}\\ dp_{i - 1,1} & \text{if } a_i = a_{i - 2} + 1\\ \end{cases}

由于第 n 个人有可能说真话也有可能说假话，所以答案为 dp_{n,0} + dp_{n,1} 对 10^9+7 取模的结果。

注意随时取模。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[200010][2],a[200010];
signed main(){
    int t;
    cin >> t;
    while(t--){
        memset(dp,0,sizeof dp);
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++) cin >> a[i];
        dp[1][1] = 1;
        if(a[1]) dp[1][0] = 0;
        else dp[1][0] = 1;
        for(int i = 2;i <= n;i++){
            dp[i][1] = dp[i - 1][0];
            if(a[i] == a[i - 1]) dp[i][0] = dp[i - 1][0];
            if(a[i] == a[i - 2] + 1) dp[i][0] += dp[i - 1][1];
            dp[i][1] %= 998244353;
            dp[i][0] %= 998244353;
        }
        cout << (dp[n][0] + dp[n][1]) % 998244353 << '\n';
    }
}