1 ноя 2022 в 11:40

MEX sequences

Ожидает приглашения

Code Forces 1613D (1900)

Какими могут быть МЕХ-последовательности? $\forall x_{i}\quad |x_{i} - MEX(x_{1},x_{2},..., x_{i})| \leq 1$ . Тогда если $MEX(x_{1},x_{2},..., x_{i}) = x$ , то $x_{i} \in \{x, x+1, x - 1 \,(елси \,x>0)\}$ . Тогда МЕХ-последовательности могут быть либо либо

Давайте считать динамическое программирование $dp1_{i}$ $dp1_{i}[j] -$ количество MEX-С подпоследовательностей первого типа на префиксе длины i с MEX равным j и аналогично $dp2_{i}, dp2_{i}[j] -$ MEX - подпоследовательностей второго типа на префиксе длины i с MEX равным j.

Пусть x текущий элемент последовательности.

В позициях где x < j - 1 или x > j + 1 ничего не меняется.

x = j - 1.

Только можем добавить в МЕХ-последовательности второго типа и МЕХ последовательности не меняется. $dp2_{i + 1}[x + 1] = dp2_{i + 1}[x + 1] + dp2_i[x + 1].$
Можем добавить в МЕХ-последовательности перого типа и МЕХ последовательности не меняется. $dp1_{i + 1}[x + 1] = dp1_{i + 1}[x + 1] + dp1_i[x + 1 ].$

x = j. Только можем добавить п МЕХ-последовательности перого типа и МЕХ последовательности увиличится на 1. $dp1_{i + 1}[x + 1] = dp1_{i + 1}[x + 1] + dp1_i[x].$

x = j + 1.

Можем добавить в МЕХ-последовательности перого типа и получим МЕХ-последовательности второго типа и МЕХ последовательности не меняется. $dp2_{i + 1}[x - 1] = dp2_{i + 1}[x - 1] + dp1_i[x - 1].$
Можем добавить в МЕХ-последовательности втрого типа и МЕХ последовательночти не меняется. $dp2_{i + 1}[x - 1] = dp2_{i + 1}[x - 1] + dp2_i[x - 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';
    }
}

Использовано решение.

Хабы: