47 lines
1.7 KiB
Markdown
47 lines
1.7 KiB
Markdown
---
|
||
id: 5900f50c1000cf542c51001e
|
||
title: 'Завдання 415: Титанічні множини'
|
||
challengeType: 5
|
||
forumTopicId: 302084
|
||
dashedName: problem-415-titanic-sets
|
||
---
|
||
|
||
# --description--
|
||
|
||
Набір точок ґратки $S$ називається титанічною множиною, якщо існує лінія, що проходить рівно через дві точки в $S$.
|
||
|
||
Прикладом титанічної множини є $S = \\{(0, 0), (0, 1), (0, 2), (1, 1), (2, 0), (1, 0), (1, 0)\\}$, де лінія, що проходить через (0, 1) та (2, 0) не проходить через будь-які інші точки в $S$.
|
||
|
||
З іншого боку, множина {(0, 0), (1, 1), (2, 2), (4, 4)} не є титанічною множиною, оскільки пряма, що проходить через дві точки у множині, також проходить через дві інші.
|
||
|
||
Для будь-якого додатного цілого числа $N$, нехай $T(N)$ — кількість титанічних множин $S$, кожна точка яких ($x$ $y$) задовільняє $0 ≤ x$, $y ≤ N$. Можна перевірити, що $T(1) = 11$, $T(2) = 494$, $T(4) = 33\\,554\\,178$, $T(111)\bmod {10}^8 = 13\\,500\\,401$ і $T({10}^5)\bmod {10}^8 = 63\\,259\\,062$.
|
||
|
||
Знайдіть $T({10}^{11})\bmod {10}^8$.
|
||
|
||
# --hints--
|
||
|
||
`titanicSets()` має повернути `55859742`.
|
||
|
||
```js
|
||
assert.strictEqual(titanicSets(), 55859742);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function titanicSets() {
|
||
|
||
return true;
|
||
}
|
||
|
||
titanicSets();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|