1.4 KiB
1.4 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f5091000cf542c51001b | Задача 408: Прийнятні шляхи через сітку | 5 | 302076 | problem-408-admissible-paths-through-a-grid |
--description--
Назвемо точки ґратки (x, y) неприйнятними, якщо x, y, а x + y — це всі додатні ідеальні квадрати.
Наприклад, (9, 16) є неприйнятними, а (0, 4), (3, 1) та (9, 4) — прийнятні.
Розглянемо шлях від точки (x_1, y_1) до точки (x_2, y_2), використовуючи лише одиничні кроки на північ чи схід. Назвемо такий шлях прийнятним, якщо жодна з його проміжних точок не є неприйнятною.
Нехай P(n) — це кількість прийнятних шляхів з (0, 0) до (n, n). Можна перевірити, що P(5) = 252, P(16) = 596\\,994\\,440, а P(1\\,000)\bmod 1\\,000\\,000\\,007 = 341\\,920\\,854.
Знайдіть P(10\\,000\\,000)\bmod 1\\,000\\,000\\,007.
--hints--
admissiblePaths() має повернути 299742733.
assert.strictEqual(admissiblePaths(), 299742733);
--seed--
--seed-contents--
function admissiblePaths() {
return true;
}
admissiblePaths();
--solutions--
// solution required