fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MOD 1000003
  4.  
  5.  
  6. typedef long long int ll;
  7. ll arr[1000000+10];
  8. ll cal[1000000+10];
  9.  
  10. ll factorial_mod(ll value, ll counter) {
  11.  
  12.   if(counter == 0) return 1;
  13.   ll ans;
  14.   ans = 1;
  15.   for(ll i = 1; i <= counter; i++){
  16.     ans = ((ans % MOD) * (value % MOD)) % MOD;
  17.     value--;
  18.   }
  19.   return ans;
  20. }
  21.  
  22. ll bigMod(ll base, ll power, ll mod) {
  23.   if(power == 0) return 1;
  24.   if(power == 1) return base;
  25.   if(power % 2 == 0) {
  26.     ll value = bigMod(base,power/2,mod) % mod;
  27.     return (value * value) % mod;
  28.   }
  29.   if(power % 2 == 1) {
  30.     ll value = bigMod(base,power-1,mod) % mod;
  31.     return ((base % mod) * (value)) % mod;
  32.   }
  33. }
  34.  
  35.  
  36.  
  37.  
  38. int main(void)
  39. {
  40.     ll T,t;
  41.     scanf("%lld",&T);
  42.     arr[1] = 1;
  43.     arr[0] = 1;
  44.     arr[2] = 2;
  45.     for(ll i = 3; i <= 1000000; i++){
  46.         arr[i] = ((arr[i-1] % MOD) * (i % MOD)) % MOD;
  47.     }
  48.     for(ll i = 0; i <= 1000000; i++){
  49.         cal[i] = -1;
  50.     }
  51.     for(t = 1; t <= T; t++){
  52.         ll n,r;
  53.         scanf("%lld %lld",&n,&r);
  54.         ll lob = arr[n];
  55.         ll hor = arr[r];
  56.         if(cal[r] == -1) {
  57.         hor = bigMod(hor,MOD-2,MOD);
  58.         cal[r] = hor;
  59.         }
  60.         else {
  61.             hor = cal[r];
  62.         }
  63.         ll baki = arr[n-r];
  64.         if(cal[n-r] == -1) {
  65.         baki = bigMod(baki,MOD-2,MOD);
  66.         cal[n-r] = baki;
  67.         }
  68.         else {
  69.             baki = cal[n-r];
  70.         }
  71.         ll ans = ((((lob % MOD) * (hor % MOD)) % MOD ) * (baki % MOD)) % MOD;
  72.         printf("Case %lld: %lld\n",t,ans);
  73.     }
  74.     return 0;
  75. }
  76.  
Runtime error #stdin #stdout 0.02s 19096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7k9opq
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!