Вечірка#5329

Вечірка (Розбір)

Відповіддю до задачі буде значення $C_{n}^{k} m o d 9929$ C_n^{k}~mod~9929. Оскільки слід знайти біноміальний коефіцієнт по модулю, постараємося при обчисленнях уникнути ділення. Для цього скористаємося співвідношенням $C_{n}^{k} = C_{n - 1}^{k} + C_{n - 1}^{k - 1}, C_{n}^{0} = 1$ C_n^{k} = C_{n - 1}^{k} + C_{n - 1}^{k - 1}, C_n^{0} = 1.

Задачу можна вирішити також за формулою

C_{n}^{k} = \frac{n !}{k ! \cdot ( n - k )!} = \frac{n \cdot ( n - 1 ) \cdot ( n - 2 ) \cdot ... \cdot ( n - k + 1 )}{1 \cdot 2 \cdot 3 \cdot ... \cdot k} = \frac{n}{1} \cdot \frac{n - 1}{2} \cdot \frac{n - 2}{3} \cdot ... \cdot \frac{n - k + 1}{k}

C_n^{k} = {n! \over k! \cdot (n - k)!} = {n \cdot (n - 1) \cdot (n - 2) \cdot ... \cdot (n - k + 1) \over 1 \cdot 2 \cdot 3 \cdot ... \cdot k} = {n \over 1} \cdot {n - 1 \over 2} \cdot {n - 2 \over 3} \cdot ... \cdot {n - k + 1 \over k}

замінивши ділення множенням на обернене число по модулю $9929$ . Зазначимо, що число $9929$ просте. Тобто $n / i = n \cdot (i^{- 1}) m o d 9929$ n / i = n \cdot (i^{-1})~mod~9929.

За теоремою Ферма $i^{9928} m o d 9929 = 1$ i^{9928}~mod~9929 = 1 або $(i \cdot i^{9927}) m o d 9929 = 1$ (i \cdot i^{9927})~mod~9929 = 1, звідки оберненим до $i$ по модулю $9929$ буде $i^{9927} m o d 9929$ i^{9927}~mod~9929. Таким чином

(i^{- 1}) m o d 9929 = i^{9927} m o d 9929

(i^{-1})~mod~9929 = i^{9927}~mod~9929

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

Оголосимо константи і масив $c nk$ , для якого $c nk [n] [k] = C_{n}^{k} m o d 9929$ cnk[n][k] = C_n^{k}~mod~9929.

#define MAX 510
#define MOD 9929
int cnk[MAX][MAX];

Функція c обчислює значення біноміального коефіцієнта $C_{n}^{k} m o d 9929$ C_n^{k}~mod~9929.

int c(int n, int k)
{
  if (cnk[n][k] > 0) return cnk[n][k];
  if (n - k < k) return c(n,n-k);
  if (!k) return cnk[n][k] = 1;
  return cnk[n][k] = (c(n-1,k) + c(n-1,k-1)) % MOD;
}

C++

Основна частина програми. Ініціалізуємо масив $c nk$ нулями. Читаємо вхідні дані.

memset(cnk,0,sizeof(cnk));
scanf("%d %d",&n,&k);

Обчислюємо і виводимо відповідь.

printf("%d\n",c(n,k));

Реалізація алгоритму – циклічна

Оголосимо константи і масив $c nk$ , для якого $c nk [n] [k] = C_{n}^{k}$ cnk[n][k] = C_n^{k}.

#define MAX 502
#define MOD 9929
int cnk[MAX][MAX];

Функція FillCnk заповнює масив $c nk$ біноміальними коефіцієнтами.

void FillCnk(void)
{
  int n, k;
  memset(cnk,0,sizeof(cnk));

Ініціалізація $c nk [n] [0] = C_{n}^{0} = 1$ cnk[n][0] = C_n^{0} = 1.

  for(n = 0; n < MAX; n++) cnk[n][0] = 1;

Проводимо обчислення, скориставшись формулою $C_{n}^{k} = C_{n - 1}^{k} + C_{n - 1}^{k - 1}$ C_n^{k} = C_{n - 1}^{k} + C_{n - 1}^{k - 1}. Обчислення проводимо по модулю $M O D$ .

  for(n = 1; n < MAX; n++)
  for(k = 1; k <= MAX; k++)
    cnk[n][k] = (cnk[n-1][k] + cnk[n-1][k-1]) % MOD;
}

Основна частина програми. Заповнюємо масив біноміальних коефіцієнтів.

FillCnk();

Читаємо вхідні дані. Обчислюємо і виводимо відповідь.

scanf("%d %d",&n,&k);
printf("%d\n",cnk[n][k]);

Реалізація алгоритму – обернене по модулю

Функція pow обчислює $x^{n} m o d p$ x^n~mod~p.

int pow(int x, int n, int 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$ : $x^{- 1} m o d p$ x^{-1}~mod~p ( $p$ просте).

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

Функція Cnk обчислює значення біноміального коефіцієнта $C_{n}^{k}$ C_n^{k} по модулю $p$ . Для цього вираз

r es = r es \cdot (n - i + 1) / i

res = res \cdot (n - i + 1) / i

перепишемо у вигляді

r es = (r es \cdot (n - i + 1) \cdot (i^{- 1} m o d p)) m o d p

res = (res \cdot (n - i + 1) \cdot (i^{-1}~mod~p))~mod~p

int Cnk(int n, int k, int p)
{
  int res = 1;
  if (k > n - k) k = n - k;
  for (int i = 1; i <= k; i++)
    res = ((res * (n - i + 1)) % p * inverse(i, p)) % p;
  return res;
}

C++

Основна частина програми. Читаємо вхідні дані.

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

Обчислюємо і виводимо відповідь.

res = Cnk(n, k, 9929);
printf("%d\n", res);

Java реалізація

import java.util.*;

public class Main
{
  static int dp[][];
  static int MOD = 9929;
  
  static int Cnk(int n, int k)
  {
    if (n == k) return 1;
    if (k == 0) return 1;
    if (dp[n][k] != -1) return dp[n][k];
    return dp[n][k] = (Cnk(n - 1, k - 1) + Cnk(n - 1, k)) % MOD;
  }
	
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int k = con.nextInt();
    dp = new int[n+1][k+1];
    for(int i = 0; i <= n; i++)
      Arrays.fill(dp[i],-1);
    
    int res = Cnk(n,k);
    System.out.println(res);
    con.close();
  }
}

Java

Java реалізація – ітераційна, довга арифметика

import java.util.*;
import java.math.*;

public class Main
{
  static BigInteger Cnk(int n, int k)
  {
    BigInteger res = BigInteger.ONE;
    BigInteger MOD = BigInteger.valueOf(9929);
    BigInteger p = BigInteger.valueOf(n);
    BigInteger q = BigInteger.valueOf(1);
    for (int i = 0; i < k; i++)
    {
      res = res.multiply(p).multiply(q.modInverse(MOD)).mod(MOD);
      p = p.subtract(BigInteger.ONE);
      q = q.add(BigInteger.ONE);
    }
    return res;
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int k = con.nextInt();
    	  
    BigInteger res = Cnk(n,k); 
    System.out.println(res);
    con.close();
  }
}

Java

Python реалізація

Функція Cnk обчислює значення біноміального коефіцієнта $C_{n}^{k} m o d 9929$ C_n^{k}~mod~9929 і запам'ятовує його значення в ячейці $d p [n] [k]$ dp[n][k].

def Cnk(n, k, dp):
  if n == k: return 1
  if k == 0: return 1
  if dp[n][k] != -1: return dp[n][k]
  dp[n][k] = (Cnk(n - 1, k - 1, dp) + Cnk(n - 1, k, dp)) % 9929
  return dp[n][k]

Основна частина програми. Читаємо вхідні дані.

n, k = map(int, input().split())

Ініціалізуємо двовимірний список для запам'ятовування значень:

d p [x] [y] = C_{n}^{k} m o d 9929

dp[x][y] = C_n^{k}~mod~9929

dp = [[-1] * 501 for _ in range(501)]

Обчислюємо і виводимо відповідь.

print(Cnk(n, k, dp))