Code Forces 1613D (1900)
Ссылка на задачу.
Какими могут быть МЕХ-последовательности? . Тогда если
, то
. Тогда МЕХ-последовательности могут быть либо
либо
Давайте считать динамическое программирование количество MEX-С подпоследовательностей первого типа на префиксе длины i с MEX равным j и аналогично
MEX - подпоследовательностей второго типа на префиксе длины i с MEX равным j.
Пусть x текущий элемент последовательности.
В позициях где x < j - 1 или x > j + 1 ничего не меняется.
x = j - 1.
Только можем добавить в МЕХ-последовательности второго типа и МЕХ последовательности не меняется.
Можем добавить в МЕХ-последовательности перого типа и МЕХ последовательности не меняется.
x = j. Только можем добавить п МЕХ-последовательности перого типа и МЕХ последовательности увиличится на 1.
x = j + 1.
Можем добавить в МЕХ-последовательности перого типа и получим МЕХ-последовательности второго типа и МЕХ последовательности не меняется.
Можем добавить в МЕХ-последовательности втрого типа и МЕХ последовательночти не меняется.
Получаем что в каждом шаге (i -> i + 1) dp1 и dp2 меняется в некоторых позициях. Поэтому можем хранить только однономерные динамики.
#include <iostream>
#include <vector>
const size_t MAX = 998244353; // в задаче ответ должен быть по модлю
size_t Sum(size_t x, size_t y) {
x %= MAX;
y %= MAX;
x = (x + y) % MAX;
return x;
}
size_t Test(const std::vector<size_t> &given_array) {
std::vector<size_t> dp1(given_array.size() + 2);
std::vector<size_t> dp2(given_array.size() + 2);
dp1[0] = 1;
for (const auto x: given_array) {
dp1[x + 1] = Sum(dp1[x + 1], dp1[x + 1]);
dp1[x + 1] = Sum(dp1[x + 1], dp1[x]);
if (x > 0) {
dp2[x - 1] = Sum(dp2[x - 1], dp2[x - 1]);
dp2[x - 1] = Sum(dp2[x - 1], dp1[x - 1]);
}
dp2[x + 1] = Sum(dp2[x + 1], dp2[x + 1]);
}
size_t ans = 0;
for (const auto res: dp1) {
ans = Sum(ans, res);
}
for (const auto res: dp2) {
ans = Sum(ans, res);
}
ans += MAX;
return (ans - 1) % MAX;
}
int main() {
size_t tests_amount = 0;
std::cin >> tests_amount;
for (size_t test = 0; test < tests_amount; ++test) {
size_t n = 0;
std::cin >> n;
std::vector<size_t> given_array;
given_array.reserve(n);
for (size_t i = 0; i < n; ++i) {
size_t x = 0;
std::cin >> x;
given_array.push_back(x);
}
std::cout << Test(given_array) << '\n';
}
}
Использовано решение.