Задача 382
Генерирование многоугольников

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

Множество положительных чисел S генерирует многоугольник P, если:

  • никакие две стороны P не имеют одинаковую длину,
  • длина каждой стороны P содержится в S, и
  • S не содержит никаких других значений.

Например:
Множество {3, 4, 5} генерирует многоугольник со сторонами 3, 4 и 5 (треугольник).
Множество {6, 9, 11, 24} генерирует многоугольник со сторонами 6, 9, 11 и 24 (четырехугольник).
Множества {1, 2, 3} и {2, 3, 4, 9} не генерируют никакие многоугольники.

Рассмотрим последовательность s, определенную следующим образом:

  • s1 = 1, s2 = 2, s3 = 3
  • sn = sn-1 + sn-3 для n > 3.

Пусть Un будет множеством {s1, s2, ..., sn}. Например, U10 = {1, 2, 3, 4, 6, 9, 13, 19, 28, 41}.
Пусть f(n) будет количеством подмножеств Un, которые генерируют хотя бы один многоугольник.
Например, f(5) = 7, f(10) = 501 и f(25) = 18635853.

Найдите последние 9 цифр f(1018).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net