https://codeforces.com/contest/2061/problem/C
题目大意
给出 $n \ (1 \le n \le 2 \times 10^5)$ 个人。每个人可以说谎或诚实。诚实的人总说真话，说谎的人可以说真话或者假话。任意两个说谎的人不相邻。每个人 $i$ 做出了如下论断：$i$ 左侧有 $a_i \ (0 \le a_i \le n)$ 个人说谎。问最多有多少种可能的说谎诚实的组合。结果模 $998244353$。
简要题解
观察：
- 如果 $a_i > i$ 则这个人只能说谎。因为左侧没有足够的人。
- 因为相邻的两个人不能说谎，因此 $i - 1$ 或者 $i - 2$ 必然是诚实的。
有了这两个观察我们就可以转移了。
设 $dph[i]$ 和 $dpl[i]$ 分别为第 $i$ 个人诚实和说谎的方案数。
$i = 0$ 和 $i = 1$ 可以特殊处理。
对于其他的 $i$。如果 $i$ 位置说谎则 $i - 1$ 位置必然为诚实，也就是 $dpl[i] = dph[i - 1]$。
如果 $a[i] \le i$ 则：
- $i - 1$ 为诚实，则 $i$ 与 $i - 1$ 左侧说谎的人数要一致即 $a[i] = a[i - 1]$：$dph[i] \gets dph[i - 1]$。
- $i - 1$ 说谎，则 $i - 2$ 诚实，此时 $i$ 比 $i - 2$ 多一个说谎的人，即 $a[i] = a[i - 2] + 1$：$dph[i] \gets dph[i - 2]$。
最终答案就是 $dph[n - 1] + dpl[n - 1]$。
（虽然只是个 C 题，但是感觉真没那么简单）
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
template<long long Mo=998244353> struct ModInt {
static long long MO;
static void setMo(long long mo) { MO = mo; }
long long x;
ModInt(long long x=0) : x(x){ norm(); }
friend istream &operator>>(istream& in, ModInt &B) { in>>B.x; return in; }
friend ostream &operator<<(ostream& out, const ModInt &B) {
out<<B.x; return out; }
// ModInt operator=(int x_) { x=x_; norm(); return *this; }
void norm() { x = (x%MO + MO) % MO; }
long long get() { return x; }
ModInt operator-() const { return ModInt(MO - x); }
ModInt operator+=(const ModInt &B) { x+=B.x; if(x>=MO) x-=MO; return *this; }
ModInt operator-=(const ModInt &B) { x-=B.x; if(x<0) x+=MO; return *this; }
ModInt operator*=(const ModInt &B) { x=x*B.x%MO; return *this; }
ModInt operator+(const ModInt &B) const { ModInt ans=*this; return ans+=B; }
ModInt operator-(const ModInt &B) const { ModInt ans=*this; return ans-=B; }
ModInt operator*(const ModInt &B) const { ModInt ans=*this; return ans*=B; }
ModInt operator^(long long n) const {
ModInt a=*this; ModInt ans(1);
while(n) { if(n&1) ans*=a; a*=a; n>>=1; }
return ans;
}
ModInt inv() const { return (*this)^(MO-2); } // if MO is prime
ModInt operator/=(const ModInt &B) { (*this)*=B.inv(); return *this; }
ModInt operator/(const ModInt &B) const { ModInt ans=*this; return ans/=B; }
bool operator<(const ModInt &B) const { return x<B.x; }
bool operator==(const ModInt &B) const { return x==B.x; }
bool operator!=(const ModInt &B) const { return x!=B.x; }
};
template<long long Mo> long long ModInt<Mo>::MO = Mo;
typedef ModInt<998244353> Mint;
// typedef ModInt<1'000'000'007> Mint;
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
vector<Mint> dph(n);
vector<Mint> dpl(n);
if (a[0]) {
dpl[0] = 1;
} else {
dpl[0] = dph[0] = 1;
}
for (int i = 1; i < n; i++) {
if (a[i] > i) { // only can be liar
dpl[i] = dph[i - 1];
} else {
// liar
dpl[i] = dph[i - 1];
// honest
if (i == 1) {
if (a[i]) {
dph[i] = 1;
} else {
dph[i] = dph[i - 1];
}
} else {
if (a[i] == a[i - 1]) {
dph[i] += dph[i - 1];
}
if (a[i] == a[i - 2] + 1) {
dph[i] += dph[i - 2];
}
}
}
}
Mint ans = dpl[n - 1] + dph[n - 1];
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] D. Kevin and Numbers - IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)