---

Problem 382

---

Generating polygons

A polygon is a flat shape consisting of straight line segments that are joined to form a closed chain or circuit. A polygon consists of at least three sides and does not self-intersect.

A set S of positive numbers is said to generate a polygon P if:

• no two sides of P are the same length,
• the length of every side of P is in S, and
• S contains no other value.

For example:
The set {3, 4, 5} generates a polygon with sides 3, 4, and 5 (a triangle).
The set {6, 9, 11, 24} generates a polygon with sides 6, 9, 11, and 24 (a quadrilateral).
The sets {1, 2, 3} and {2, 3, 4, 9} do not generate any polygon at all.

Consider the sequence s, defined as follows:

• s₁ = 1, s₂ = 2, s₃ = 3
• s_n = s_n-1 + s_n-3 for n > 3.

Let U_n be the set {s₁, s₂, …, s_n}. For example, U₁₀ = {1, 2, 3, 4, 6, 9, 13, 19, 28, 41}.
Let f(n) be the number of subsets of U_n which generate at least one polygon.
For example, f(5) = 7, f(10) = 501 and f(25) = 18635853.

Find the last 9 digits of f(10¹⁸).

---

生成多边形

多边形是指由直线段相连接构成封闭路径的平面图形。一个多边形至少有三条边，而且边不能自交。

我们称正整数集S生成了多边形P，如果：

• P的任意两条边长度都不相等，
• P的每一条边的长度都在集合S中，而且
• S中不包含除P的边长外其它的值。

举例来说：
集合{3, 4, 5}生成边长为3、4、5的多边形（三角形）。
集合{6, 9, 11, 24}生成边长为6、9、11、24的多边形（四边形）。
集合{1, 2, 3}和{2, 3, 4, 9}不能生成多边形。

考虑按如下方式定义的序列s：

• s₁ = 1，s₂ = 2，s₃ = 3
• 当n > 3时，s_n = s_n-1 + s_n-3。

记U_n为集合{s₁, s₂, …, s_n}。例如，U₁₀ = {1, 2, 3, 4, 6, 9, 13, 19, 28, 41}。
记f(n)为能够生成至少一个多边形的U_n子集的数目。
例如，f(5) = 7，f(10) = 501以及f(25) = 18635853。

求f(10¹⁸)的最后9位数字。

---