Advertisement
Saleh127

LO 1067

Nov 28th, 2020
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.92 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5.  
  6. ll m=1000003;
  7. ll fact[1000006];
  8. ll factinv[1000006];
  9.  
  10. ll bigmod(ll a,ll c,ll m)
  11. {
  12. if(c==0) return 1;
  13.  
  14. ll x=bigmod(a,c/2,m);
  15.  
  16. x=x*x%m;
  17.  
  18. if(c%2==1)
  19. {
  20. x=(x*a)%m;
  21. }
  22.  
  23. return x;
  24. }
  25.  
  26. void precal()
  27. {
  28. fact[0]=1;
  29.  
  30. ll i;
  31.  
  32. for(i=1; i<1000005; i++)
  33. {
  34. fact[i]=(fact[i-1]*i)%m;
  35. }
  36. for(i=0; i<1000005; i++)
  37. {
  38. factinv[i]=bigmod(fact[i],m-2,m);
  39. }
  40. }
  41.  
  42. ll ncr(ll n,ll r)
  43. {
  44. ll ans=((fact[n]%m)*(factinv[r]%m))%m;
  45.  
  46. ans=((ans%m)*(factinv[n-r]%m))%m;
  47.  
  48. return ans;
  49. }
  50.  
  51.  
  52. int main()
  53. {
  54. ios_base::sync_with_stdio(0);
  55. cin.tie(0);
  56. cout.tie(0);
  57.  
  58. precal();
  59.  
  60. test
  61. {
  62. ll n,r;
  63. cin>>n>>r;
  64. cout<<"Case "<<cs<<": "<<ncr(n,r)<<endl;
  65. }
  66.  
  67.  
  68. return 0;
  69. }
  70.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement