Pair the people#11288

Pair the people (Editorial)

Let $f (n)$ represent the number of different ways that all $n$ people can join the dance. For example,

$f (1) = 1$ f(1) = 1, one person dances by himself;
$f (2) = 2$ f(2) = 2, for two people, there are two options: either dance separately or as a pair;

Consider the $n$ -th person:

If he dances alone, the remaining $n - 1$ n - 1 people can join the dance in $f (n - 1)$ f(n - 1) ways
The $n$ -th person can choose any of the $n - 1$ n - 1 people as a partner. The remaining $n - 2$ n - 2 people can join the dance in $f (n - 2)$ f(n - 2) ways.

Thus we have the relation:

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

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

Example

Let there be $n = 3$ n = 3 people. They can join the dance in $4$ ways:

if the third person dances separately: ${1, 2, 3}, {{1, 2}, 3}$ \{1, 2, 3\}, \{\{1, 2\}, 3\};
if the third person dances in a pair: ${1, {2, 3}}, {2, {1, 3}}$ \{1, \{2, 3\}\}, \{2, \{1, 3\}\}.

Compute $f (3)$ using a formula:

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

Algorithm implementation

Declare a modulo constant and an array to store the answers: $d p [n] = f (n)$ dp[n] = f(n).

#define MOD 1000000007
long long dp[100001];

Read the input value of $n$ .

scanf("%d", &n);

Compute the values sequentially for $f (1), f (2), ..., f (n)$ f(1), f(2), ..., f(n), storing each result in the $d p$ array.

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

Print the answer.

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

Python implementation

Declare the modulo constant $M O D$ , which will be used for the calculations.

MOD = 1000000007

Read the input value of $n$ .

n = int(input())

Declare a list for storing the results, where $d p [n] = f (n)$ dp[n] = f(n).

dp = [0] * (n + 1)

Compute the values sequentially for $f (1), f (2), ..., f (n)$ f(1), f(2), ..., f(n), storing each result in the $d p$ array.

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 the answer.

print(dp[n])