1.8 KiB
1.8 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f4eb1000cf542c50fffd | 問題 382: 多角形を生成する | 5 | 302046 | problem-382-generating-polygons |
--description--
多角形とは、閉路を形成するように結合された直線分からなる平面図形です。 多角形は少なくとも 3 本の辺で構成され、それ自体と交差することはありません。
以下の条件をすべて満たす正の数 S の集合が多角形 P を生成するものとします。
Pのいずれの 2 辺も長さが異なる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 を考えます。
s_1 = 1,s_2 = 2,s_3 = 3n > 3のとき、s_n = s_{n - 1} + s_{n - 3}
U_n を集合 \\{s_1, s_2, \ldots, s_n\\} と定義します。 例えば、U_{10} = \\{1, 2, 3, 4, 6, 9, 13, 19, 28, 41\\} です。
U_n の部分集合のうち、少なくとも 1 つの多角形を生成する部分集合の数を f(n) とします。
例えば、f(5) = 7, f(10) = 501, f(25) = 18\\,635\\,853 です。
f({10}^{18}) の下位 9 桁を求めなさい。
--hints--
generatingPolygons() は 697003956 を返す必要があります。
assert.strictEqual(generatingPolygons(), 697003956);
--seed--
--seed-contents--
function generatingPolygons() {
return true;
}
generatingPolygons();
--solutions--
// solution required