fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define sd(x) scanf("%d",&x);
  6. #define slld(x) scanf("%lld",&x);
  7. #define LL long long
  8. #define LD long double
  9. #define PB push_back
  10. #define MP make_pair
  11. #define F first
  12. #define S second
  13. #define Fill(a, b) memset(a, b, sizeof(a))
  14. #define INF 2000000009
  15.  
  16. typedef pair<int,int> PII;
  17. typedef vector<int> VI;
  18.  
  19. #define N 2000010
  20.  
  21. LL fact[N],inv[N],mod = 1000000007;
  22.  
  23. LL power(LL a, LL n)
  24. {
  25.     LL ret = 1;
  26.     while(n)
  27.     {
  28.         if(n&1)ret = (ret*a)%mod;
  29.         n>>=1;
  30.         a=(a*a)%mod;
  31.     }
  32.     return ret;
  33. }
  34.  
  35. void pre()
  36. {
  37.     fact[0] = 1;
  38.     for(int i=1;i<N;i++)
  39.     {
  40.         fact[i] = (i*fact[i-1])%mod;
  41.     }
  42. }
  43.  
  44. LL inve(LL n)
  45. {
  46.     LL ans = fact[n];
  47.     return power(ans,mod-2);
  48. }
  49.  
  50. LL comb(LL n, LL r)
  51. {
  52.     if(n<r)return 0;
  53.     LL ans = (inve(n-r) *inve(r))%mod;
  54.     ans = (ans*fact[n])%mod;
  55.     //cout<<n<<" "<<r<<" "<<ans<<endl;
  56.     return ans;
  57. }
  58.  
  59. LL get(int n)
  60. {//cout<<n<<endl;
  61.     if(n<2)return 1;
  62.     LL ans;
  63.     if(n&(n+1))
  64.     {
  65.         ans = get(n/2) *get(n/2 - 1) *2;
  66.         ans%=mod;
  67.         return (ans*comb(n-1,n/2))%mod;
  68.     }
  69.     else
  70.     {
  71.         ans = get(n/2);
  72.         ans = (ans*ans)%mod;
  73.         return (ans*comb(n-1,n/2))%mod;
  74.     }
  75. }
  76.  
  77. LL dp[N];
  78.  
  79. /*void compute()
  80. {
  81.     dp[0] = 1;
  82.     dp[1] = 1;
  83.     int j=1;
  84.     for(int i=2;i<10000;i++)
  85.     {
  86.         for(int x = j;;x--)
  87.         {
  88.             if(i-x-1 > j)break;
  89.             dp[i] += (((dp[x]*dp[i-x-1])%mod) * comb(i-1,x))%mod;
  90.         }
  91.         dp[i] %= mod;
  92.         if(!(i&(i+1))) j = i;
  93.         //cout<<i<<" "<<dp[i]<<endl;
  94.     }
  95. }*/
  96.  
  97. void solve()
  98. {
  99.     int n,m;
  100.     sd(n);sd(m);
  101.     assert(((n&(n+1)) == 0) || (((n+1)&(n+2)) == 0));
  102.     mod = m;
  103.     pre();
  104.     //compute();
  105.     cout<<get(n)<<endl;;
  106. }
  107.  
  108. int main()
  109. {
  110.     //cout<<"done!!\n";
  111. 	int t=1;
  112. 	//scanf("%d",&t);
  113. 	for(int i=1;i<=t;i++)
  114. 	{
  115. 		solve();
  116. 	}
  117. }
  118.  
Runtime error #stdin #stdout #stderr 0s 50344KB
comments ()
stdin
copy 
Tester Solution
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:101: void solve(): Assertion `((n&(n+1)) == 0) || (((n+1)&(n+2)) == 0)' failed.
https://ideone.com/0rIKGQ
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!