1.5 KiB
1.5 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f5181000cf542c51002a | Завдання 427: n-послідовності | 5 | 302097 | problem-427-n-sequences |
--description--
Послідовність цілих чисел S = \\{s_i\\} називається $n$-послідовністю, якщо вона має n елементи, і кожен елемент s_i задовольняє нерівність 1 ≤ s_i ≤ n. Таким чином, сумарно є n^n різних $n$-послідовностей.
Наприклад, послідовність S = \\{1, 5, 5, 10, 7, 7, 7, 2, 3, 7\\} - 10-послідовність.
Для будь-якої послідовності S, припустимо L(S) є довжиною найдовшої дотичної підпослідовності S з тим же значенням. Наприклад, для даної послідовності S вище, L(S) = 3, через три послідовні сімки.
Припустимо f(n) = \sum L(S) для всіх $n$-послідовностей S.
Наприклад, f(3) = 45, f(7) = 1\\,403\\,689 і f(11) = 481\\,496\\,895\\,121.
Знайдіть f(7\\,500\\,000)\bmod 1\\,000\\,000\\,009.
--hints--
nSequences() має повернути 97138867.
assert.strictEqual(nSequences(), 97138867);
--seed--
--seed-contents--
function nSequences() {
return true;
}
nSequences();
--solutions--
// solution required