Lemurian parties - easy#11269

Lemurian parties - easy (Editorial)

For $n$ seats, some species will be represented by two lemurs, and some by one. Let $i$ pairs of lemurs be chosen (that is, $i$ species are represented by two individuals). The number of ways to make such a choice is $C_{k}^{i}$ C_k^i. After this, there will be $n - 2 i$ n - 2i free seats in the VIP area. These seats can be occupied by lemurs from $k - i$ k - i remaining species, choosing one lemur from each. The number of ways to choose such lemurs is calculated by the formula $C_{k - i}^{n - 2 i}$ C_{k - i}^{n - 2i}.

Since the value of $i$ can take any integer from $0$ to $k$ , the final answer is obtained as the sum over all possible values of $i$ :

i = 0 \sum k C_{k}^{i} \cdot C_{k - i}^{n - 2 i}

\sum_{i = 0}^k C_k^i \cdot C_{k - i}^{n - 2i}

Example

Let's consider a second example, where there are $k = 4$ k = 4 pairs of lemurs and $n = 3$ n = 3 seats in the VIP area. Using the formula, we get:

i = 0 \sum k C_{4}^{i} \cdot C_{4 - i}^{3 - 2 i} = C_{4}^{0} \cdot C_{4}^{3} + C_{4}^{1} \cdot C_{3}^{1} = 4 + 12 = 16

\sum_{i = 0}^k C_4^i \cdot C_{4 - i}^{3 - 2i} = C_4^0 \cdot C_4^3 + C_4^1 \cdot C_3^1 = 4 + 12 = 16

Let's list only the nonzero terms. We'll consider the value $C_{n}^{k}$ C_n^k to be zero if any of the following three inequalities hold: $k < 0$ k < 0, $n < 0$ n < 0 или $k > n$ k > n.

Let us denote the lemurs by the letters ${a, a, b, b, c, c, d, d}$ \{a, a, b, b, c, c, d, d\}, where identical letters correspond to lemurs of the same species.

The term $C_{4}^{0} \cdot C_{4}^{3} = 4$ C_4^0 \cdot C_4^3 = 4 corresponds to the situation where no pair of lemurs of the same species is chosen, that is, each of the three selected lemurs belongs to a different species. The four possible selections are as follows:

Now consider the term $C_{4}^{1} \cdot C_{3}^{1} = 12$ C_4^1 \cdot C_3^1 = 12. In this case, two lemurs are chosen from one species (there are $4$ possible ways to do this). For the remaining one seat, one lemur is chosen from the three remaining species. Thus, there are a total of $12$ possible selections.

It is clear that it is impossible to place two lemurs from two different species in only $3$ seats. Therefore, all the remaining terms of the sum are equal to zero.

Algorithm implementation

Declare the constants.

#define MAX 1000001
#define MOD 1000000007

Let us define the following arrays:

$f a c t$ contains the factorials of numbers modulo $M O D$ ;
$f a c t in v$ factinv contains the values inverse to the factorials of numbers modulo $M O D$ :

fact[n] = n! mod 1000000007
factinv[n] = n! -1 mod 1000000007

typedef long long ll;
ll fact[MAX], factinv[MAX];

The function pow computes the power of a number modulo $p$ : $x^{n} m o d p$ x^n~mod~p.

ll pow(ll x, ll n, ll p)
{
  if (n == 0) return 1;
  if (n % 2 == 0) return pow((x * x) % p, n / 2, p);
  return (x * pow(x, n - 1, p)) % p;
}

The function inverse finds the number that is the modular inverse of $x$ with respect to a prime modulo $p$ . Since $p$ is a prime number, by Fermat's little theorem the following equality holds:

x^{p - 1} m o d p = 1 f or e v er y 1 \leq x < p

x^{p-1}~mod~p~=~1~for~every~1 \le x < p

This equality can be rewritten as:

(x \cdot x^{p - 2}) m o d p = 1,

(x \cdot x^{p-2})~mod~p~=~1,

which means that the modular inverse of $x$ is $x^{p - 2} m o d p$ x^{p-2}~mod~p.

ll inverse(ll x, ll p)
{
  return pow(x, p - 2, p);
}

The function Cnk computes the value of the binomial coefficient using the following formula:

C_{n}^{k} = \frac{n !}{k ! ( n - k )!}

C_n^k = \frac{n!}{k! (n - k)!}

ll Cnk(int n, int k)
{
  return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;
}

The main part of the program. Read the input data.

scanf("%d %d", &k, &n);

Fill the factorial arrays $f a c t$ and $f a c t in v$ factinv.

fact[0] = 1;
for (i = 1; i < MAX; i++)
  fact[i] = (fact[i - 1] * i) % MOD;

factinv[0] = 1;
for (i = 1; i < MAX; i++)
   factinv[i] = inverse(fact[i], MOD);

C++

Compute the answer using the formula $\sum_{i = 0}^{k} C_{k}^{i} \cdot C_{k - i}^{n - 2 i}$ \sum_{i = 0}^k C_k^i \cdot C_{k - i}^{n - 2i}. The value of the binomial coefficient $C_{n}^{k}$ C_n^k is considered to be zero if any of the following three conditions hold: $k < 0$ k < 0, $n < 0$ n < 0 or $k > n$ k > n.

res = 0;
for (i = 0; i <= k; i++)
{
  if (n - 2 * i < 0 || k - i < 0 || n - 2 * i > k - i) continue;
  res = (res + Cnk(k, i) * Cnk(k - i, n - 2 * i)) % MOD;
}

Print the answer.

printf("%lld\n", res);