Розбір

The answer to the problem will be the value of $C_{n}^{k} m o d 9929$ . Since we need to find the binomial coefficient by modulo, we’ll try to avoid division during calculations. To achieve this, use the relation: $C_{n}^{k} = C_{n - 1}^{k} + C_{n - 1}^{k - 1}, C_{n}^{0} = 1$ .

The problem can also be solved using the formula:

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}

by replacing division with multiplication by the inverse number modulo $9929$ . Note that the number $9929$ is a prime. That is, $n / i = n \cdot (i^{- 1}) m o d 9929$ .

According to Fermat’s theorem, $i^{9928} m o d 9929 = 1$ or $(i \cdot i^{9927}) m o d 9929 = 1$ , hence the inverse of $i$ modulo $9929$ will be $i^{9927} m o d 9929$ . Thus,

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

Algorithm realization

Declare the constants and array $c nk$ , where $c nk [n] [k] = C_{n}^{k} m o d 9929$ .

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

The c function computes the value of the binomial coefficient $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;
}

The main part of the program. Initialize the $c nk$ array with zeros. Read the input data.

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

Compute and print the answer.

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

Algorithm realization – loops

Declare the constants and array $c nk$ , where $c nk [n] [k] = C_{n}^{k}$ .

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

The FillCnk function fills the $c nk$ array with binomial coefficients.

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

Initialize $c nk [n] [0] = C_{n}^{0} = 1$ .

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

Perform the computation using the formula $C_{n}^{k} = C_{n - 1}^{k} + C_{n - 1}^{k - 1}$ modulo $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;
}

The main part of the program. Fill the array of binomial coefficients.

FillCnk();

Read the input data. Compute and print the answer.

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

Algorithm realization – inverse modulo

The pow function computes $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;
}

The inverse function computes the number that is the inverse of $x$ modulo $p$ : $x^{- 1} m o d p$ (where $p$ is prime).

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

The Cnk function computes the value of the binomial coefficient $C_{n}^{k}$ modulo $p$ . To achieve this, rewrite an expression

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

in the form

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

The main part of the program. Read the input data.

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

Compute and print the answer.

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

Java realization

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 realization – loops, long arithmetic

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 realization

The Cnk function computes the value of the binomial coefficient $C_{n}^{k} m o d 9929$ and memoizes its value in the cell $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]

The main part of the program. Read the input data.

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

Initialize a two-dimensional list for memoizing the values:

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

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

Compute and print the answer.

print(Cnk(n, k, dp))