Əyləncə gecəsi#5329

Əyləncə gecəsi (Həll təhlili)

Verilən problem üçün cavab $C_{n}^{k} m o d 9929$ C_n^{k}~mod~9929 olacaq. Binomial əmsalı modula görə hesablamaq lazımdırsa, hesablamalar zamanı bölmədən qaçmağa çalışacağıq. Bunun üçün $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 formulasından istifadə edəcəyik.

Problemi aşağıdakı formuladan istifadə edərək də həll etmək olar

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}

bölməni modula görə tərs ədədə vurma ilə əvəz edərək, $9929$ moduluna görə. Qeyd edək ki, $9929$ sadə ədəddir. Deməli, $n / i = n \cdot (i^{- 1}) m o d 9929$ n / i = n \cdot (i^{-1})~mod~9929.

Fermanın teoreminə görə $i^{9928} m o d 9929 = 1$ i^{9928}~mod~9929 = 1 və ya $(i \cdot i^{9927}) m o d 9929 = 1$ (i \cdot i^{9927})~mod~9929 = 1, buradan $9929$ moduluna görə $i$ -nin tərs ədədi $i^{9927} m o d 9929$ i^{9927}~mod~9929 olacaq. Beləliklə

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

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

Algoritminin realizasiyası

Sabitləri və $c nk$ massivini elan edək, burada $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 funksiyası $C_{n}^{k} m o d 9929$ C_n^{k}~mod~9929 binomial əmsalının dəyərini hesablayır.

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

Proqramın əsas hissəsi. $c nk$ massivini sıfırlarla inicializasiya edirik. Giriş məlumatlarını oxuyuruq.

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

Hesablayırıq və cavabı çıxarırıq.

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

Algoritmin realizasiyası – dövri

Sabitləri və $c nk$ massivini elan edək, burada $c nk [n] [k] = C_{n}^{k}$ cnk[n][k] = C_n^{k}.

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

FillCnk funksiyası binomial əmsallarla $c nk$ massivini doldurur.

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

$c_{n} k [n] [0] = C_{n}^{0} = 1$ c_nk[n][0] = C_n^{0} = 1 inicializasiyası.

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

Hesablamaları aparırıq, $C_{n}^{k} = C_{n - 1}^{k} + C_{n - 1}^{k - 1}$ C_n^{k} = C_{n - 1}^{k} + C_{n - 1}^{k - 1} formulundan istifadə edərək. Hesablamaları $M O D$ moduluna görə aparırıq.

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

Proqramın əsas hissəsi. Binomial əmsallarını massivə doldururuq.

FillCnk();

Giriş məlumatlarını oxuyuruq. Hesablayırıq və cavabı çıxarırıq.

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

Algoritmin realizasiyası – modula görə tərs

pow funksiyası $x^{n} m o d p$ x^n~mod~p hesablayır.

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 funksiyası $x$ -ə görə tərs rəqəmi hesablayır, $p$ modulu ilə: $x^{- 1} m o d p$ x^{-1}~mod~p ( $p$ sadə).

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

Cnk funksiyası binomial əmsalın dəyərini $C_{n}^{k}$ C_n^{k} moduluna görə $p$ hesablayır. Bunun üçün ifadə

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

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

şəklində yenidən yazmışıq

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Hesablayırıq və cavabı çıxarırıq.

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

Java realizasiyası

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 realizasiyası – iterativ, uzun arifmetika

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 realizasiyası

Cnk funksiyası binomial əmsalın dəyərini $C_{n}^{k} m o d 9929$ C_n^{k}~mod~9929 hesablayır və onun dəyərini $d p [n] [k]$ dp[n][k] hüceyrəsində yadda saxlayır.

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]

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Dəyərləri yadda saxlamaq üçün ikiölçülü siyahını inicializasiya edirik:

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)]

Hesablayırıq və cavabı çıxarırıq.

print(Cnk(n, k, dp))