Düzülüş#11552

Düzülüş (Həll təhlili)

Sinifdə oğlanların sayı $b = m - n$ b = m - n bərabərdir. Oğlanlar hamısı fərqləndirilə bildiyinə görə, onların düzülmə üsullarının sayı bərabərdir:

b! = (m - n)!

b! = (m - n)!

$b$ oğlanın ətrafında qızların qoyula biləcəyi $b + 1$ b + 1 mövqe yaranır:

Cəmisi $n$ qız var. Buna görə də qızların qoyula biləcəyi $b + 1$ b + 1 mövqedən $n$ fərqli mövqe seçməliyik:

C_{b + 1}^{n}

C_{b+1}^n

Əgər $n > b + 1$ n > b + 1, cavab $0$ bərabərdir.

Qızlar da fərqləndirilə bilir, yəni onları da yer dəyişdirmək olar.

Beləliklə, bütün şagirdlərin sıraya düzülebilmə üsullarının sayı bərabərdir:

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

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

Nümunə

$m = 3$ m = 3, $n = 2$ n = 2 testini nəzərdən keçirək.

Oğlanların sayı $b = m - n = 3 - 2 = 1$ b = m - n = 3 - 2 = 1 bərabərdir. Cavab bərabərdir:

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 testini nəzərdən keçirək.

Oğlanların sayı $b = m - n = 4 - 2 = 2$ b = m - n = 4 - 2 = 2 bərabərdir. Cavab bərabərdir:

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

Alqoritmin Yerləşdirilməsi

Massivlər elan edək:

$f a c t$ ədədlərin faktoriyallarını $M O D$ üzrə saxlayır,
$f a c t in v$ factinv bu faktoriyalların əks qiymətlərini $M O D$ üzrə saxlayır:

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 funksiyası modul üzrə ədədin dərəcəsini hesablamaq üçündür: $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 funksiyası $x$ üçün sadə modul $p$ üzrə tərs ədədi tapır. Çünki $p$ sadə ədəddir, fermatın kiçik teoreminə görə:

x^{p - 1} m o d p = 1 h ə r 1 \leq x < p u ¨ c \c u ¨ n

x^{p - 1}~mod~p = 1~hər~1 \le x < p~üçün

Bu, $(x \cdot x^{p - 2}) m o d p = 1$ (x \cdot x^{p - 2})~mod~p = 1 formasında yenidən yazıla bilər, buradan $x$ -ə tərs olan ədəd $x^{p - 2} m o d p$ x^{p - 2}~mod~p olduğu nəticəsi çıxır.

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

Cnk funksiyası binomial koeffisiyenti aşağıdakı formula ilə hesablayır:

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

Proqramın əsas hissəsi. Faktoriyalların $f a c t$ massivi və əks faktoriyalların $f a c t in v$ factinv massivi dolur.

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++

Testlərin sayını $t es t s$ oxuyuruq.

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

Cari testin məlumatlarını oxuyuruq.

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

Oğlanların sayını $b = m - n$ b = m - n hesablayırıq.

  b = m - n;

Cavabı formula ilə hesablayıb çap edirik:

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