Разбор

Ответом к задаче будет значение $C_{n}^{k} m o d 9929$ . Поскольку следует найти биномиальный коэффициент по модулю, постараемся при вычислениях избежать деления. Для этого воспользуемся соотношением $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}

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

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

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

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

Объявим константы и массив $c nk$ , для которого $c nk [n] [k] = C_{n}^{k} m o d 9929$ .

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

Функция c вычисляет значение биномиального коэффициента $C_{n}^{k} m o d 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 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}$ .

#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$ .

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

Проводим вычисления, воспользовавшись формулой $C_{n}^{k} = C_{n - 1}^{k} + C_{n - 1}^{k - 1}$ . Вычисления проводим по модулю $MO 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$ .

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$ ( $p$ простое).

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

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

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

перепишем в виде

res = (res \cdot (n - i + 1) \cdot (i^{- 1} m o d p)) m o d 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;
}

Основная часть программы. Читаем входные данные.

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 реализация – итерационная, длинная арифметика

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

Python реализация

Функция Cnk вычисляет значение биномиального коэффициента $C_{n}^{k} m o d 9929$ и запоминает его значение в ячейке $d p [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 = [[-1] * 501 for _ in range(501)]

Вычисляем и выводим ответ.

print(Cnk(n, k, dp))