Arrangement#11552

Arrangement (Editorial)

The number of boys in the class is $b = m - n$ b = m - n. Since all boys are distinguishable, the number of ways to arrange them is

b! = (m - n)!

b! = (m - n)!

Around the $b$ boys, there are $b + 1$ b + 1 positions where girls can be placed:

There are $n$ girls in total. Therefore, we need to choose $n$ distinct positions out of the $b + 1$ b + 1 available positions in which to place the girls:

C_{b + 1}^{n}

C_{b+1}^n

If $n > b + 1$ n > b + 1, then the answer is $0$ .

The girls are also distinguishable, so they can be permuted.

Thus, the total number of ways to arrange all the students in a row is equal to

C_{b + 1}^{n} \cdot b! \cdot n!

C_{b+1}^n \cdot b! \cdot n!

Example

Consider the test case $m = 3$ m = 3, $n = 2$ n = 2.

The number of boys is $b = m - n = 3 - 2 = 1$ b = m - n = 3 - 2 = 1. The answer is equal to

C_{2}^{2} \cdot 1! \cdot 2! = 1 \cdot 1 \cdot 2 = 2

C_2^2 \cdot 1! \cdot 2! = 1 \cdot 1 \cdot 2 = 2

Consider the test case $m = 4$ m = 4, $n = 2$ n = 2.

The number of boys is $b = m - n = 4 - 2 = 2$ b = m - n = 4 - 2 = 2. The answer is equal to

C_{3}^{2} \cdot 2! \cdot 2! = 3 \cdot 2 \cdot 2 = 12

C_3^2 \cdot 2! \cdot 2! = 3 \cdot 2 \cdot 2 = 12

Algorithm implementation

Let us define the arrays:

$f a c t$ , which stores the factorials of numbers modulo $M O D$ ,
$f a c t in v$ factinv, which stores the modular inverses of these factorials modulo $M O D$ :

f a c t [n] = n! m o d 1000000007 f a c t in v [n] = n!^{- 1} m o d 1000000007

fact[n] = n!~mod~1000000007 \\ factinv[n] = n!^{-1}~mod~1000000007

#define MAX 1000001
#define MOD 1000000007
ll fact[MAX], factinv[MAX];

The function pow computes the power of a number modulo a given modulus:

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 inverse function 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 holds:

x^{p - 1} m o d p = 1 для любого 1 \leq x < p

x^{p - 1}~mod~p = 1~для~любого~1 \le x < p

This can be rewritten as $(x \cdot x^{p - 2}) m o d p = 1$ (x \cdot x^{p - 2})~mod~p = 1, from which it follows 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 Cnk function computes the binomial coefficient using the 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. Fill the arrays of factorials $f a c t$ and inverse factorials $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++

Read the number of test cases $t es t s$ .

scanf("%d", &tests);
while (tests--)
{

Read the data for the current test case.

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

Compute the number of boys $b = m - n$ b = m - n.

  b = m - n;

Compute and print the answer using the formula:

C_{b + 1}^{n} \cdot b! \cdot n!

C_{b+1}^n \cdot b! \cdot n!

  res = ((fact[n] * fact[b]) % MOD * Cnk(b + 1, n)) % MOD;
  printf("%lld\n", res);
}