Как стать автором
Поиск
Написать публикацию
Обновить

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)\}. Тогда МЕХ-последовательности могут быть либо (0, 1,1,...,1, ..., x - 1, x - 1, x - 1 ,..., x - 1, x,x,...,x) либо (0, 1,1,...,1, ..., x - 1, x - 1, x - 1 ,..., x - 1, x + 1,x + 1,...,x + 1).

Давайте считать динамическое программирование 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.

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

  2. Можем добавить в МЕХ-последовательности перого типа и МЕХ последовательности не меняется. 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.

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

  2. Можем добавить в МЕХ-последовательности втрого типа и МЕХ последовательночти не меняется. 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';
    }
}

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

Теги:
Хабы:
Данная статья не подлежит комментированию, поскольку её автор ещё не является полноправным участником сообщества. Вы сможете связаться с автором только после того, как он получит приглашение от кого-либо из участников сообщества. До этого момента его username будет скрыт псевдонимом.