Advertisement
rotti321

Combinari(n,k) cu invers modular

Feb 18th, 2022
31
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define MOD 9901
  3. using namespace std;
  4.  
  5. int putere(int a,int b){
  6. int p=1; ///a^b=a*a*...*a (de b ori)
  7. for(int i=1;i<=b;i++)
  8. p=(p*a)%MOD;
  9. return p;
  10. }
  11. int factorial(int n)
  12. {
  13. if(n<=1) return 1;
  14. return n*factorial(n-1)%MOD;
  15. }
  16. int inv_mod(int x)
  17. {
  18. return putere(x, MOD-2);
  19. }
  20. int comb(int n,int k)
  21. {
  22. return factorial(n)*inv_mod(k)*inv_mod(n-k)%MOD;
  23. }
  24. int main() {
  25. int n,k;
  26. cin>>n>>k;
  27. cout<<comb(n,k);
  28. // cout<<factorial(n);
  29. ///cout<<putere(k, 10);
  30. //<<" "<<inv_mod(k)<<" "<<inv_mod(n-k);
  31. }
Advertisement
RAW Paste Data Copied
Advertisement