nCr%pを計算する


難易度 簡単に
よく聞かれる アクセンチュア ケイデンスインド コムリメディア オラキャブ 正方形である
動的計画法 数学

問題文

問題「ComputenCr%p」は、pを法とする二項係数を見つける必要があることを示しています。 したがって、最初に二項係数について知る必要があります。 これについては、以前の投稿ですでに説明しました。 あなたはそれをチェックすることができます .

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

説明

nCr = 5C2 = 10
nCr%p = 10%6 = 4
そこで、二項係数の式を使って5C2を計算しました。 次に、値を法として取りました。

nCr%pを計算する

アプローチ

二項係数の計算に関する前回の投稿。 最初に、nCrを解くために必要な値を計算しました。 使用しました 動的計画法 問題を解決するために、しかしそれから私達はnCrの値を計算するだけでした。 ある数pを法とする二項係数ではありません。 素朴なアプローチは、最初に二項係数を計算し、次にpを法とすることです。 ただし、この計算には制限があります。 オーバーフローが発生するため、大きな数の二項係数を計算することはできません。 したがって、整数のオーバーフローに陥ることなく正しい結果を生成できる方法を見つける必要があります。

私たちにできることのXNUMXつは、二項係数の計算中に係数を取り続けることです。 したがって、前の投稿のソリューションからの唯一の変更は、計算中にモジュラスを使用することです。 したがって、再帰式は少し変更されますが、遷移は同じままです。 また、現在の二項係数は、以前と同じ状態に依存しています。

コード

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は指定された入力です。 これは、二項係数を計算するときに、外側のループとXNUMXつの内側のループがあったためです。

スペースの複雑さ

O(R)、中間値を格納する配列を作成したため、スペースの複雑さは線形です。