Codeforces Round #518 (Div. 1) [Thanks, Mail.Ru!]: A. Array Without Local Maximums
問題
歯脱けの数列が与えられるので下に凸になるように値を埋める方法の数を答えよ
解法
概要
DPやるだけ。最大値$K = 200$が定数で乗って$O(KN)$。
実装
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP3R(i, m, n) for (int i = int(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
using namespace std;
template <int32_t MOD>
struct mint {
int64_t value;
mint() = default;
mint(int64_t value_) : value(value_) {}
inline mint<MOD> operator + (mint<MOD> other) const { int64_t c = this->value + other.value; return mint<MOD>(c >= MOD ? c - MOD : c); }
inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
};
constexpr int MOD = 998244353;
mint<MOD> solve(int n, vector<int> const & a) {
array<array<mint<MOD>, 201>, 2> cur, prv;
cur = {};
REP3 (a_i, 1, 201) if (a[0] == -1 or a_i == a[0]) {
cur[false][a_i] = 1;
}
REP3 (i, 1, n) {
prv = cur;
cur = {};
mint<MOD> high = 0;
REP3R (a_i, 1, 201) {
cur[true][a_i] += high;
high += prv[true][a_i];
}
REP3 (a_i, 1, 201) {
cur[true][a_i] += prv[false][a_i];
cur[true][a_i] += prv[ true][a_i];
}
mint<MOD> low = 0;
REP3 (a_i, 1, 201) {
cur[false][a_i] += low;
low += prv[false][a_i];
low += prv[ true][a_i];
}
if (a[i] != -1) {
REP3 (a_i, 1, 201) if (a_i != a[i]) {
cur[false][a_i] = 0;
cur[ true][a_i] = 0;
}
}
}
return accumulate(ALL(cur[true]), mint<MOD>());
}
int main() {
int n; cin >> n;
vector<int> a(n);
REP (i, n) cin >> a[i];
cout << solve(n, a).value << endl;
return 0;
}