fork download 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 1 << 20;
  4. int n , mod;
  5. int add(int a , int b){
  6.     int res = a + b;
  7.     if(res >= mod){
  8.         return res - mod;
  9.     }
  10.     return res;
  11. }
  12. int mult(int a , int b){
  13.     long long res = a;
  14.     res *= b;
  15.     if(res >= mod){
  16.         return res % mod;
  17.     }
  18.     return res;
  19. }
  20. int power(int a , int b){
  21.     int res = 1;
  22.     while(b){
  23.         if(b & 1){
  24.             res = mult(res , a);
  25.         }
  26.         a = mult(a , a);
  27.         b >>= 1;
  28.     }
  29.     return res;
  30. }
  31. int fact[N];
  32. int ifact[N];
  33. void pre(){
  34.     fact[0] = 1;
  35.     for(int i = 1 ; i <= n ; ++i){
  36.         fact[i] = mult(fact[i - 1] , i);
  37.     }
  38.     ifact[n] = power(fact[n] , mod - 2);
  39.     for(int i = n - 1 ; i >= 0 ; --i){
  40.         ifact[i] = mult(ifact[i + 1] , i + 1);
  41.     }
  42. }
  43. int c(int n , int r){
  44.     return mult(fact[n] , mult(ifact[r] , ifact[n - r]));
  45. }
  46. int solve(int n){
  47.     if(n == 1){
  48.         return 1;
  49.     }
  50.     int res = solve(n >> 1);
  51.     res = mult(res , res);
  52.     res = mult(res , c(n - 1 , n >> 1));
  53.     return res;
  54. }
  55. int main(){
  56.     cin >> n >> mod;
  57.     n += !(n & 1);
  58.     pre();
  59.     cout << solve(n);
  60. }
Runtime error #stdin #stdout 0s 11656KB
comments ()
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/gVMEij
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!