57 lines
3.3 KiB
Markdown
57 lines
3.3 KiB
Markdown
|
---
|
|||
|
|
id: 5900f54c1000cf542c51005e
|
|||
|
|
title: 'Завдання 478: Комбінації'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 302155
|
|||
|
|
dashedName: problem-478-mixtures
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Розгляньмо комбінації трьох речовин: $A$, $B$ та $C$. Комбінації можна описати за співвідношенням кількості $A$, $B$, та $C$ в ній, тобто, $(a : b : c)$. Наприклад, комбінація, що описана співвідношенням (2 : 3 : 5), містить 20% $A$, 30% $B$ та 50% $C$.
|
|||
|
|
|
|||
|
|
В контексті цієї проблеми ми не можемо відокремити окремі компоненти із комбінації. Однак ми можемо комбінувати різні кількості різних комбінацій, щоб утворювати комбінації з новими співвідношеннями.
|
|||
|
|
|
|||
|
|
Наприклад, скажімо, що у нас є три комбінації зі співвідношеннями (3 : 0 : 2), (3 : 6 : 11) та (3 : 3 : 4). Змішуючи 10 одиниць першої, 20 одиниць другої та 30 одиниць третьої, ми отримуємо нову комбінацію зі співвідношенням (6 : 5 : 9), оскільки: ($10 \times \frac{3}{5} + 20 \times \frac{3}{20} + 30 \times \frac{3}{10}$ : $10 \times \frac{0}{5} + 20 \times \frac{6}{20} + 30 \times \frac{3}{10}$ : $10 \times \frac{2}{5} + 20 \times \frac{11}{20} + 30 \times \frac{4}{10}$) = (18 : 15 : 27) = (6 : 5 : 9)
|
|||
|
|
|
|||
|
|
Однак з трьома однаковими комбінаціями неможливо сформувати співвідношення (3 : 2 : 1), оскільки кількість $B$ завжди менша за кількість $C$.
|
|||
|
|
|
|||
|
|
Нехай $n$ буде позитивним цілим числом. Припустимо, що для кожної трійки чисел $(a, b, c)$ з $0 ≤ a, b, c ≤ n$ та $gcd(a, b, c) = 1$, ми маємо комбінацію зі співвідношенням $(a : b : c)$. Нехай $M(n)$ - це множина всіх таких комбінацій.
|
|||
|
|
|
|||
|
|
Наприклад, $M(2)$ містить 19 комбінацій з наступними співвідношеннями:
|
|||
|
|
|
|||
|
|
{(0 : 0 : 1), (0 : 1 : 0), (0 : 1 : 1), (0 : 1 : 2), (0 : 2 : 1), (1 : 0 : 0), (1 : 0 : 1), (1 : 0 : 2), (1 : 1 : 0), (1 : 1 : 1), (1 : 1 : 2), (1 : 2 : 0), (1 : 2 : 1), (1 : 2 : 2), (2 : 0 : 1), (2 : 1 : 0), (2 : 1 : 1), (2 : 1 : 2), (2 : 2 : 1)}.
|
|||
|
|
|
|||
|
|
Нехай $E(n)$ - це кількість підмножин $M(n)$, які можуть створити комбінацію зі співвідношенням (1 : 1 : 1), тобто комбінацію з рівними частинами $A$, $B$ та $C$.
|
|||
|
|
|
|||
|
|
Ми можемо перевірити, що $E(1) = 103$, $E(2) = 520\\,447$, $E(10)\bmod {11}^8 = 82\\,608\\,406$ and $E(500)\bmod {11}^8 = 13\\,801\\,403$.
|
|||
|
|
|
|||
|
|
Знайдіть $E(10\\,000\\,000)\bmod {11}^8$.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`mixtures()` має повернути `59510340`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(mixtures(), 59510340);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function mixtures() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
mixtures();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|