Розташування#11552

Розташування (Розбір)

Кількість хлопчиків у класі дорівнює $b = m - n$ b = m - n. Оскільки хлопчики всі відрізняються, число способів їх розставити дорівнює

b! = (m - n)!

b! = (m - n)!

Навколо $b$ хлопчиків утворюється $b + 1$ b + 1 позиція, куди можна поставити дівчаток:

Всього дівчаток $n$ . Тому нам слід вибрати $n$ різних позицій із $b + 1$ b + 1, куди можна поставити дівчаток:

C_{b + 1}^{n}

C_{b+1}^n

Якщо $n > b + 1$ n > b + 1, то відповідь дорівнює $0$ .

Дівчатка також відрізняються, отже їх можна переставляти.

Таким чином, кількість способів, якими можна розставити в ряд усіх учнів, дорівнює

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

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

Приклад

Розглянемо тест $m = 3$ m = 3, $n = 2$ n = 2.

Число хлопчиків дорівнює $b = m - n = 3 - 2 = 1$ b = m - n = 3 - 2 = 1. Відповідь дорівнює

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

Розглянемо тест $m = 4$ m = 4, $n = 2$ n = 2.

Число хлопчиків дорівнює $b = m - n = 4 - 2 = 2$ b = m - n = 4 - 2 = 2. Відповідь дорівнює

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

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

Оголосимо масиви:

$f a c t$ містить факторіали чисел по модулю $M O D$ ,
$f a c t in v$ factinv містить обернені значення до цих факторіалів по модулю $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];

Функція pow обчислює степінь числа по модулю: $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;
}

Функція inverse знаходить число, обернене до $x$ по простому модулю $p$ . Так як $p$ — просте число, то за малою теоремою Ферма виконується рівність:

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

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

Його можна переписати у вигляді $(x \cdot x^{p - 2}) m o d p = 1$ (x \cdot x^{p - 2})~mod~p = 1, звідки слідує, що оберненим до $x$ є число $x^{p - 2} m o d p$ x^{p - 2}~mod~p.

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

Функція Cnk обчислює біноміальний коефіцієнт за формулою:

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;
}

Основна частина програми. Заповнюємо масиви факторіалів $f a c t$ та обернених факторіалів $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++

Читаємо кількість тестів $t es t s$ .

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

Читаємо дані поточного тесту.

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

Обчислюємо кількість хлопчиків $b = m - n$ b = m - n.

  b = m - n;

Обчислюємо та виводимо відповідь за формулою:

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);
}