გამოთვალეთ nCr% p


Რთული ტური Easy
ხშირად ეკითხებიან Accenture კადენს ინდოეთი კომლი მედია ოლა კაბინები Square
დინამიური პროგრამირება მათემატიკის

პრობლემის განცხადება

პრობლემა "გამოთვალეთ nCr% p" აცხადებს, რომ თქვენ მოეთხოვებათ binomial კოეფიციენტის მოდული p. თქვენ ჯერ უნდა იცოდეთ ბინომის კოეფიციენტის შესახებ. ამის შესახებ უკვე განვიხილეთ წინა პოსტში. თქვენ შეგიძლიათ შეამოწმოთ ეს აქ.

მაგალითი

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

განმარტება

nCr = 5C2 = 10
nCr% p = 10% 6 = 4
ასე რომ, ჩვენ გამოვთვალეთ 5C2 ბინომური კოეფიციენტის ფორმულის გამოყენებით. შემდეგ აიღო მოდული მნიშვნელობაზე.

გამოთვალეთ nCr% p

მიდგომა

წინა პოსტში ბინომური კოეფიციენტის გაანგარიშებასთან დაკავშირებით. რაც ჩვენ გავაკეთეთ, ჯერ გამოთვალეს მნიშვნელობები, რომლებიც საჭიროა nCr– ის გადასაჭრელად. ჩვენ გამოვიყენეთ დინამიური პროგრამირება პრობლემის გადასაჭრელად, მაგრამ შემდეგ ჩვენ მხოლოდ nCr– ის მნიშვნელობას ვანგარიშობდით. არა ბინომის კოეფიციენტის მოდული ზოგიერთი რიცხვი p. გულუბრყვილო მიდგომა იქნება ჯერ ბინომის კოეფიციენტის გამოთვლა და შემდეგ მოდულის p. მაგრამ ამ გაანგარიშებაზე არსებობს შეზღუდვა. თქვენ არ შეგიძლიათ გამოანგარიშოთ ბინომური კოეფიციენტები დიდი რიცხვებისთვის, რადგან ეს გამოიწვევს გადავსებას. ასე რომ, ჩვენ უნდა მოვიძიოთ გზა, რომელსაც შეუძლია სწორი შედეგის გამომუშავება მთელი რიცხვის გადავსების გარეშე.

ერთი რამ, რისი გაკეთებაც შეგვიძლია, არის განაგრძოთ მოდულის მიღება, ხოლო ჩვენი ბინომის კოეფიციენტის გაანგარიშება. წინა პოსტის ამოხსნის ერთადერთი ცვლილება ისაა, რომ გამოთვლების დროს ვიღებთ მოდულს. ამრიგად, ჩვენი რეკურსიული ფორმულა ოდნავ შეიცვლება, მაგრამ გადასვლები იგივე რჩება. ამჟამინდელი ბინომის კოეფიციენტი დამოკიდებულია იმავე მდგომარეობებზე, რაც ადრე იყო.

კოდი

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

სირთულის ანალიზი

დროის სირთულე

O (N * R), სადაც N და R მოცემულია შესატანები. ეს იმიტომ ხდება, რომ როდესაც ბინომური კოეფიციენტის გაანგარიშებისას გვქონდა გარე მარყუჟი და ერთი შიდა მარყუჟი.

სივრცის სირთულე

O (R)მას შემდეგ, რაც ჩვენ შევქმენით მასივი შუალედური მნიშვნელობების შესანახად, ამრიგად, სივრცის სირთულე ხაზოვანია.