194_500.cpp

#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>

//  Максимальная длина последовательности:
const int MAX_N = 500;

//  Константы, используемые для сжатия четырех чисел в один int для экономии памяти:
const int LIMIT = 511;
const int POW2 = 9;

//  Функции перевода из сжатого состояния в нормальное и наоборот:
inline int max_to_key(uint8_t max1, uint8_t max2, uint8_t max3);
std::vector<uint8_t> key_to_max (int key);

struct State {

    uint32_t key; // сжатое состояние, которое хранит в себе позицию четырех максимумов в последовательности

    //  Конструктор
    State(uint8_t max1 = 0, uint8_t max2 = 0, uint8_t max3 = 0)
        : key(max_to_key(max1, max2, max3))
    { }

    // Получение всех следующих состояний за текущим
    std::vector<State> next_states(int curr_len) const {
        // Пытаемся вставить новый максимум в последовательность из уже имеющихся четырех максимумов
        // Рассматриваем все возможные варианты

        std::vector<State> answer;

        auto max = key_to_max(key);

        // Пытаемся вставить между нулевым и первым максимумом:
        if ( abs(max[0] - max[1]) == 1 ) {
            answer.push_back(State(std::max(max[0], max[1]), max[0], max[1]));
            answer.back().shift_right_after_insert();
        }

        // Между нулевым и вторым максимумом
        if ( abs(max[0] - max[2]) == 1) {
            answer.push_back(State(std::max(max[0], max[2]), max[0], max[1]));
            answer.back().shift_right_after_insert();
        }

        // Между первым и вторым максимумом
        if ( abs(max[1] - max[2]) == 1) {
            answer.push_back(State(std::max(max[1], max[2]), max[0], max[1]));
            answer.back().shift_right_after_insert();
        }

        for (int i = 0; i < 3; ++i)
        // После i-го максимума в конец последовательности:
            if (max[i] == curr_len) {
                answer.push_back(State(curr_len+1, max[0], max[1]));
                break;
            }

        return answer;
    }


    //  Сдвиг совпадающих позиций вправо на один после добавления нового максимума (чтобы состояние было корректным)
    void shift_right_after_insert() {
        auto max = key_to_max(key);

        for (int i = 1; i <= 2; ++i)
            if (max[0] <= max[i])
                max[i]++;

        key = max_to_key(max[0], max[1], max[2]);
    }
};

//  Оператор сравнения для контейнера std::map
inline bool operator < (const State & a, const State & b) {
    return a.key < b.key;
}

//  Класс для длинной арифметики:
struct Number {
    static const int POW10 = (int)1e9;
    static const int WIDTH = 9;
    std::vector<int> digits;

    Number(int n = 0) : digits(1, n) { }

    Number(const std::vector<int> & digits) : digits(digits) { }

    Number & operator+= (const Number & other);

    inline bool is_zero() const;
};

std::ostream & operator<< (std::ostream & os, const Number & num);

int main() {
    freopen("output.txt", "wt", stdout);

//  Состояние однозначно определяется:
//      - длиной последовательности
//      - позицией первого максимума
//      - позицией второго максимума
//      - позицией третьего максимума
//      - позицией четвертого максимума

//  Вектор, в котором будем хранить количество последовательностей для текущего состояния:
//  Чтобы избежать пятимерного вектора, будем хранить состояния в std::map
    std::vector<std::map<State, Number>> count(1+MAX_N);

//  Вектор для вычисленных сумм для каждой длины:
    std::vector<Number> sum(1+MAX_N);

//  Начальные состояния для последовательности длины 4:
    std::vector<State> start_states = {
        State(4,3,2),
        State(4,2,3),
        State(3,4,2),
        State(3,2,4),
        State(2,3,4),
        State(2,4,3),
    };

//  Две очереди, в которых будем хранить состояния, которые необходимо посетить на текущей итерации.
//  Очереди будем чередовать.
    std::vector<State> queue1((1+MAX_N)*(1+MAX_N));
    std::vector<State> queue2((1+MAX_N)*(1+MAX_N));

//  Начальная длина и конечная длина:
    int len = 4, n = MAX_N;

//  Итератор для работы с очередями (изначально идем по первой очереди):
    auto next_queue_it = queue1.begin();

//  Вносим все стартовые состояния в очередь, попутно отмечая количество состояний
//  на текущей длине и считаем начальную сумму
    for (auto & st : start_states) {
        count[len][st] = 1;
        *next_queue_it++ = st;
    }
    sum[len] = 6;

//  Флаг для чередования очередей:
    bool flag = true;

//  Переменная для нахождения практической оценки максимального размера очереди:
    int max_queue_size = 0;

//  Цикл по длине очереди (из текущей длины мы переходим в следующую длину):
    for (int len = 4; len < n; ++len) {
        //  Обеспечиваем чередование очередей
        flag = !flag;

        //  В зависимости от flag, выбираем очередь для посещения на текущей итерации:
        auto curr_queue_start = flag ? queue2.begin() : queue1.begin();
        auto curr_queue_finish = next_queue_it;

        //  И выбираем очередь для посещения на следующей итерации
        next_queue_it = flag ? queue1.begin() : queue2.begin();

        //  Подсчет количества состояний в очереди: (для оценивания)
        int queue_size = 0;
        //  Идем вдоль всех состояний, которые мы внесли в очередь на предыдущей итерации:
        for (auto curr = curr_queue_start; curr != curr_queue_finish; ++curr) {
            //  Получаем все следующие состояния:
            auto next_states = curr->next_states(len);
            ++queue_size;
            //  Если следующих состояний нет, то переходим к следующему элементу:
            if (next_states.empty())
                continue;

            //  Запоминаем текущее количество состояний перед входом во внутренний цикл:
            Number curr_count = count[len][*curr];

            //  Цикл по всем возможным переходам:
            for (auto & next : next_states) {
                //  Если мы еще не посетили это состояние
                if (count[len+1][next].is_zero()) // то вносим его в очередь для посещения на следующей итерации
                    *next_queue_it++ = next;

                //  Увеличиваем количество последовательностей в следующем состоянии
                //  на количество последовательностей в текущем состоянии:
                count[len+1][next] += curr_count;

                //  Пересчитываем суммарное количество всех последовательностей следующей длины:
                sum[len+1] += curr_count;
            }
        }

        //  Обновляем текущий максимальный размер в очереди:
        max_queue_size = std::max(max_queue_size, queue_size);
    }

//  Выводим максимальный размер в очереди:
//  std::cout << "Max queue size: " << max_queue_size << std::endl;

//  Выводим посчитанные ответы:
    for (int i = 4; i <= n; ++i)
        std::cout << std::setw(4) << i << ":\t" << sum[i] << std::endl;

    return 0;
}

// Вывод в поток для длинного числа:
std::ostream & operator<< (std::ostream & os, const Number & num) {
    os << num.digits.back();
    for (int i = (int) num.digits.size()-2; i >= 0; --i)
        os << std::setw(Number::WIDTH) << std::setfill('0') << num.digits[i];
    return os << std::setfill(' ');
}

// Оператор прибавления к числу:
Number & Number::operator += (const Number & other) {
    int carry = 0;
    int s1 = (int) this->digits.size();
    int s2 = (int) other.digits.size();
    for (int i = 0; i < s1 || i < s2 || carry; ++i) {
        int digit1 = i < s1 ? this->digits[i] : 0;
        int digit2 = i < s2 ? other.digits[i] : 0;
        carry += digit1 + digit2;
        int digit = carry % POW10;
        carry /= POW10;
        if (i < s1) {
            digits[i] = digit;
        } else {
            digits.push_back(digit);
        }
    }
    return *this;
}

//  Проверка на равенство нулю:
inline bool Number::is_zero() const {
    return digits.size() == 1 && digits[0] == 0;
}

//  Функции перевода из сжатого состояния в нормальное и наоборот:
inline int max_to_key(uint8_t max1, uint8_t max2, uint8_t max3) {
    return max3 + ((max2 + (max1 << POW2)) << POW2);
}

std::vector<uint8_t> key_to_max (int key) {
    std::vector<uint8_t> answer(3);
    answer[2] = key & LIMIT;
    key >>= POW2;
    answer[1] = key & LIMIT;
    key >>= POW2;
    answer[0] = key;
    return answer;
}