11288. Пары из людей

 

На вечеринке присутствует n людей. Каждый человек может присоединиться к танцу в одиночку или в паре с любым другим. Найдите количество различных способов, которыми все n человек могут присоединиться к танцу.

 

Вход. Одно целое число n (1 ≤ n ≤ 105).

 

Выход. Выведите количество различных способов, которыми все n человек могут присоединиться к танцу. Выведите ответ по модулю 109 + 7.

 

Пример входа

Пример выхода

3

4

 

 

РЕШЕНИЕ

динамическое программирование

 

Анализ алгоритма

Пусть f(n) – количество различных способов, которыми все n человек могут присоединиться к танцу. Например,

·        f(1) = 1, один человек танцует сам;

·        f(2) = 2, так как для двух человек имеется два варианта: либо танцевать по отдельности, либо в паре;

 

Рассмотрим n-го человека:

·        Если он танцует отдельно, то остальные n – 1 человек могут присоединиться к танцу f(n – 1) способами.

·        n-ый человек может взять себе в пару любого из n – 1 людей. Остальные n2 человек могут присоединиться к танцу f(n2) способами.

 

Таким образом имеем соотношение:

f(n) = f(n – 1) + (n – 1) * f(n – 2)

 

Пример

Пусть имеется n = 3 людей. Они могут присоединиться к танцу 4 способами:

·        если третий человек танцует отдельно: {1, 2, 3}, {{1, 2}, 3};

·        если третий человек танцует в паре:  {1, {2, 3}}, {2, {1, 3}}.

Вычислим f(3) по формуле:

f(3) = f(2) + 2 * f(1) = 2 + 2 * 1 = 4

 

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

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

 

#define MOD 1000000007

long long dp[100001];

 

Читаем входное значение n.

 

scanf("%d", &n);

 

Последовательно вычисляем значения f(1), f(2), …, f(n), запоминая результаты в массиве dp.

 

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 реализация

Объявим модуль MOD, по которому будут производиться вычисления.

 

MOD = 1000000007

 

Читаем входное значение n.

 

n = int(input())

 

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

 

dp = [0] * (n + 1)

 

Последовательно вычисляем значения f(1), f(2), …, f(n), запоминая результаты в списке dp.

 

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])