Анализатор последовательностей

Многие задачи в спортивном программировании из раздела динамического программирования сводятся к задаче отыскания формулы какой-либо последовательности.

Формула может быть в замкнутом виде, когда ты просто подставляешь аргументы и разом получаешь результат за время O(1), или в динамической, рекуррентной форме, когда для вычисления i-го члена надо вычислить предыдующие.

Классический пример замкнутой формы - это сумма ряда n положительных чисел:

S(n)=n*(n-1)/2.

А для динамической, или рекуррентной формы - это, например, формула для i-го члена последовательности чисел Фибонначи:

F(i)=F(i-1)+F(i-2).

Например, вот такая задача (для школьников!).

Есть N чисел от 1 до N. Требуется разместить эти числа в ряд слева направо. Первым числом всегда идет 1. Каждое последующее может отличаться от предыдущего не больше, чем на 2. Например:

1 2 3 4 5 ...
1 3 2 4 5 ...
1 3 5 4 2 ...

и т.д. (эта задача есть на Тимусе).

Требудется найти количество возможных размещений по этому правилу для N чисел. N от 1 до 55.

Просто перебором в лоб не получится, так как вариантов будет 55! ~ 10^73, а времени дается всего одна секунда.

Судя по ограничению по времени в 1 секунду, тут просто должна быть формула.

А вот теперь подходим к сути поста. Недавно я наткнулся на волшебный сайт - Онлайн-энциклопедия целочисленных последовательностей. Там ты просто вводишь несколько известных тебе членов последовательности, а сайт по большой базе данных ищет совпадения с какими-либо известными последовательностями, и в случае наличия такого совпадения, дает исчерпывающую информацию - формулы, статистический анализ и т.д.

Итак, я нашел пяток первых значений решения задачи перебором - генерировал все возможные перестановки для i членов, для i от 1 до 8, и проверяя для каждой перестановки правильность выполнения условий размещения, считал количество вариантов.

В итоге, магия произошла. Когда я ввел вычисленные первые элементы последовательности в этот анализатор, мне просто сказали, что формула для i-го члена этой последовательсти: a(n)=a(n-1)+a(n-3)+1. И все! И по данной формуле задача решается пулей одним циклом за O(N).

Конечно, для реальных соревнований такое метод не годится, так как никто не даст доступа в интернет. Да и цель задачи несколько иная - научиться выводить такие динамические соотношения самому.

А вот в жизни - бывает, что числа уже есть, и надо быстренько как-то их обсчитать на больших размерностях, вот тут и пригодится этот волшеный анализатор, которые даст исчерпывающуй информацию о ваших числах.