Пари з людей#11288

Пари з людей (Розбір)

Нехай $f (n)$ — кількість різних способів, якими всі $n$ чоловік можуть приєднатися до танцю. Наприклад,

$f (1) = 1$ f(1) = 1, одна людина танцює сама;
$f (2) = 2$ f(2) = 2, тому що для двох людей є два варіанти: або танцювати окремо, або в парі;

Розглянемо $n$ -ту людину:

Якщо вона танцює окремо, то інші $n - 1$ n - 1 чоловік можуть приєднатися до танцю $f (n - 1)$ f(n - 1) способами.
$n$ -та людина може взяти собі в пару будь-кого з $n - 1$ n - 1 людей. Інші $n - 2$ n - 2 чоловік можуть приєднатися до танцю $f (n - 2)$ f(n - 2) способами.

Таким чином маємо співвідношення:

f (n) = f (n - 1) + (n - 1) \cdot f (n - 2)

f(n) = f(n - 1) + (n - 1) \cdot f(n - 2)

Приклад

Нехай є $n = 3$ n = 3 людей. Вони можуть приєднатися до танцю $4$ способами:

якщо третя людина танцює окремо: ${1, 2, 3}, {{1, 2}, 3}$ \{1, 2, 3\}, \{\{1, 2\}, 3\};
якщо третя людина танцює в парі: ${1, {2, 3}}, {2, {1, 3}}$ \{1, \{2, 3\}\}, \{2, \{1, 3\}\}.

Обчислимо $f (3)$ за формулою:

f (3) = f (2) + 2 \cdot f (1) = 2 + 2 \cdot 1 = 4

f(3) = f(2) + 2 \cdot f(1) = 2 + 2 \cdot 1 = 4

Реалізація алгоритму

Оголосимо модуль і масив для зберігання результатів: $d p [n] = f (n)$ dp[n] = f(n).

#define MOD 1000000007
long long dp[100001];

Читаємо вхідне значення $n$ .

scanf("%d", &n);

Послідовно обчислюємо значення $f (1), f (2), ..., f (n)$ f(1), f(2), ..., f(n), запам'ятовуючи результати в масиві $d p$ .

dp[1] = 1; dp[2] = 2;
for (i = 3; i <= n; i++)
  dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % MOD;

Виводимо відповідь.

printf("%lld\n", dp[n]);

Python реалізація

Оголосимо модуль $M O D$ , за яким будуть проводитися обчислення.

MOD = 1000000007

Читаємо вхідне значення $n$ .

n = int(input())

Оголосимо список для зберігання результатів: $d p [n] = f (n)$ dp[n] = f(n).

dp = [0] * (n + 1)

Послідовно обчислюємо значення $f (1), f (2), ..., f (n)$ f(1), f(2), ..., f(n), запам'ятовуючи результати в масиві $d p$ .

dp[1] = 1
if n > 1: dp[2] = 2
for i in range(3, n + 1):
  dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % MOD

Виводимо відповідь.

print(dp[n])