Files

49 lines
1.5 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

---
id: 5900f5181000cf542c51002a
title: 'Завдання 427: n-послідовності'
challengeType: 5
forumTopicId: 302097
dashedName: 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`.
```js
assert.strictEqual(nSequences(), 97138867);
```
# --seed--
## --seed-contents--
```js
function nSequences() {
return true;
}
nSequences();
```
# --solutions--
```js
// solution required
```