nCr % p 계산

난이도 쉽게
자주 묻는 질문 Accenture 케이던스 인도 콤리미디어 올라 택시 사각형.
동적 프로그래밍 수학조회수 23

문제 정책

"nCr % p 계산"문제는 모듈로 p 이항 계수를 찾아야 함을 나타냅니다. 따라서 먼저 이항 계수에 대해 알아야합니다. 우리는 이미 이전 게시물에서 논의했습니다. 당신은 그것을 확인할 수 있습니다 바로가기.

n = 5, r = 2, p = 6
4

설명

nCr = 5C2 = 10
nCr % p = 10 % 6 = 4
그래서 우리는 이항 계수의 공식을 사용하여 5C2를 계산했습니다. 그런 다음 모듈로 값을 가져 왔습니다.

nCr % p 계산

접근

이항 계수 계산에 관한 이전 게시물에서. 우리가 한 일은 먼저 nCr을 푸는 데 필요한 값을 계산 한 것입니다. 우리는 사용했었다 동적 프로그래밍 문제를 해결하기 위해 nCr의 값만 계산했습니다. 이항 계수 모듈로 일부 숫자 p가 아닙니다. 순진한 접근 방식은 먼저 이항 계수를 계산 한 다음 모듈로 p를 취하는 것입니다. 그러나이 계산에는 한계가 있습니다. 오버플로가 발생하므로 큰 수에 대한 이항 계수를 계산할 수 없습니다. 따라서 정수 오버플로없이 올바른 결과를 생성 할 수있는 방법을 찾아야합니다.

우리가 할 수있는 한 가지는 이항 계수를 계산하는 동안 계속해서 계수를 취하는 것입니다. 따라서 이전 게시물의 솔루션에서 유일한 변경 사항은 계산 중에 모듈러스를 사용한다는 것입니다. 따라서 재귀 공식은 약간 변경되지만 전환은 동일하게 유지됩니다. 그리고 현재 이항 계수는 이전과 동일한 상태에 의존합니다.

암호

nCr % p를 계산하는 C ++ 코드

#include<bits/stdc++.h>
using namespace std;
// this function just makes our pascal triangle
int computeBinomialCoefficientsModuloP(int n, int r, int p)
{
  int C[r+1];
    C[0] = 1;
    for (int i = 0; i <= n; i++)
    {
        // since the recursive formula is dependent on current and previous binomial coefficient on i
        // if we had run a forward loop our algorithm would have not given us a correct result
        for (int j = min(i, r); j >0 ; j--)
        {
            C[j] = (C[j - 1] + C[j])%p; // use recursive formula
        }
    }
    return C[r];
}

int main()
{
    int n,k,p;cin>>n>>k>>p;
    // here n & k do not satisfy the properties of binomial coefficient
    // then we will answer it as 0
    int val = computeBinomialCoefficientsModuloP(n, k, p);
    if(val != 0)
      cout<<val<<endl;
    else
      cout<<0<<endl;
}
5 2 4
2

nCr % p를 계산하는 Java 코드

import java.util.*;
class Main{
  // this function just makes our pascal triangle
  static int computeBinomialCoefficientsModuloP(int n, int r, int p) 
  {
  	int C[] = new int[r+1];
  	C[0] = 1;
    for (int i = 0; i <= n; i++) 
    { 
      // since the recursive formula is dependent on current and previous binomial coefficient on i
      // if we had run a forward loop our algorithm would have not given us a correct result 
      for (int j = Math.min(i, r); j >0 ; j--) 
      {
          C[j] = (C[j - 1] + C[j])%p; // use recursive formula
      }
    } 
    return C[r]; 
  }
  
  public static void main(String[] args)
  {
      Scanner sc = new Scanner(System.in);
      // here n & k do not satisfy the propertoes of binomial coefficient
      // then we will answer it as 0
      int n = sc.nextInt();
      int k = sc.nextInt();
      int p = sc.nextInt();
      int val = computeBinomialCoefficientsModuloP(n, k, p);
      if(val != 0)
        System.out.println(val);    
      else
        System.out.println(0);
   }
}
5 2 4
2

복잡성 분석

시간 복잡성

O (N * R), 여기서 N과 R은 주어진 입력입니다. 이항 계수를 계산할 때 외부 루프와 내부 루프가 하나 있었기 때문입니다.

공간 복잡성

또는), 중간 값을 저장하기 위해 배열을 만들었으므로 공간 복잡성은 선형입니다.

Translate »