Урожай абрикосов Баткена


Отправить решение Решать в редакторе

Сложность: 95%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Агроном из Баткена много лет записывает урожай абрикосов, но по модулю 998244353 (так велит странная традиция его института). Он уверен, что урожай подчиняется линейному рекуррентному закону порядка не больше k: существуют число L ≤ k и коэффициенты c[1], …, c[L], при которых для всех i ≥ L

a[i] = c[1] · a[i−1] + c[2] · a[i−2] + … + c[L] · a[i−L] (mod 998244353).

Коэффициенты агроном потерял, сохранились только первые 2k записей a[0], a[1], …, a[2k−1]. Помогите ему предсказать урожай в году N, то есть найти a[N].

Рисунок

Входные данные

В первой строке — два целых числа k и N (1 ≤ k ≤ 1000, 0 ≤ N ≤ 10¹⁸). Во второй строке — 2k целых чисел a[0], …, a[2k−1] (0 ≤ a[i] < 998244353). Гарантируется, что последовательность действительно подчиняется закону порядка не больше k.

Выходные данные

Выведите a[N] по модулю 998244353.

Пример 1

Вход:

2 10
0 1 1 2

Выход:

55

Пояснение

В первом примере это числа Фибоначчи: a[i] = a[i−1] + a[i−2], a[10] = 55. Во втором — a[i] = 2 · a[i−1] (первые 6 записей 1, 2, 4, 8, 16, 32), a[20] = 2²⁰ = 1048576.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов k ≤ 10 и N ≤ 20000.

Подсказка

Алгоритм Берлекэмпа — Мэсси находит кратчайшую рекурренту по 2L членам последовательности.


Комментарии

Еще нет ни одного комментария.