Հաշվարկել nCr% p


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Accenture Կադենս Հնդկաստան Կոմլի մեդիա Օլա Քաբս քառակուսի
Դինամիկ ծրագրավորում Մաթեմատիկա

Խնդիրի հայտարարություն

«Հաշվարկել 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 մոդուլը: Բայց այս հաշվարկի համար սահմանափակում կա: Դուք չեք կարող մեծ թվերի համար հաշվարկել Binomial գործակիցները, քանի որ դա կհանգեցնի վարարման: Այսպիսով, մենք պետք է գտնենք մի ձև, որը կարող է ճիշտ արդյունք տալ ՝ առանց ամբողջ թվաքանակի հորդելու:

Մի բան, որ մենք կարող ենք անել, շարունակել մոդուլը վերցնելն է, մինչ մեր երկիշխանության գործակիցը հաշվարկվում է: Այսպիսով, նախորդ հաղորդագրության լուծման միակ փոփոխությունն այն է, որ հաշվարկների ընթացքում մենք մոդուլ կվերցնենք: Այսպիսով, մեր ռեկուրսիվ բանաձևը մի փոքր կփոխվի, բայց անցումները մնում են նույնը: Իսկ ներկայիս երկիշխանության գործակիցը կախված է նույն վիճակներից, ինչ նախկինում էր:

Կոդ

C ++ ծածկագիր `nCr% p հաշվարկելու համար

#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

Java կոդ ՝ nCr% p հաշվարկելու համար

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N * R), որտեղ N և R տրված մուտքերն են: Դա այն պատճառով է, որ երբ մենք հաշվարկում էինք մեր Binomial գործակիցը, մենք ունեինք արտաքին օղակ և մեկ ներքին օղակ:

Տիեզերական բարդություն

ԿԱՄ), քանի որ մենք զանգված ենք պատրաստել ՝ միջանկյալ արժեքները պահելու համար, և այդպիսով տարածության բարդությունը գծային է: