Advertisement
Guest User

Untitled

a guest
Nov 27th, 2014
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.51 KB | None | 0 0
  1. for(i=0; i<5; i++)
  2. sum += factorial(p-i) % p;
  3.  
  4. ll powmod(ll a, ll b){//a^b % MOD
  5. ll x=1,y=a;
  6. while(b){
  7. if(b&1){
  8. x*=y; if(x>=MOD)x%=MOD;
  9. }
  10. y*=y; if(y>=MOD)y%=MOD;
  11. b>>=1;
  12. }
  13. return x;
  14. }
  15. ll InverseEuler(ll n){//modular inverse of n
  16. return powmod(n,MOD-2);
  17. }
  18. ll factMOD(ll n){ //n! % MOD efficient when MOD-n<n
  19. ll res=1,i;
  20. for(i=1; i<MOD-n; i++){
  21. res*=i;
  22. if(res>=MOD)res%=MOD;
  23. }
  24. res=InverseEuler(res);
  25. if(!(n&1))
  26. res= -res +MOD;
  27. }
  28. return res%MOD;
  29. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement