fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <algorithm>
  3. #include <cmath>
  4. using namespace std;
  5. #define ll long long int
  6.  
  7. const ll mod = 1e9+7;
  8.  
  9.  
  10. ll mul(ll a,ll b){
  11.     a%=mod;
  12.     b%=mod;
  13.     ll res = (a*b)%mod;
  14.     return res;
  15. }
  16.  
  17. ll add(ll a,ll b){
  18.     ll res = (a+b+mod)%mod;
  19.     return res;
  20. }
  21.  
  22. ll binpow(ll a,ll b){
  23.     ll res = 1;
  24.     while(b>0){
  25.         if(b&1)res = mul(res,a);
  26.         a = mul(a,a);
  27.         b>>=1;
  28.     }
  29.     return res;
  30. }
  31.  
  32.  
  33. ll inv(ll a){
  34.     return binpow(a,mod-2);
  35. }
  36.  
  37. ll series(ll a,ll r,ll n){
  38.     ll ans = mul(a,add(1,-binpow(r,n)));
  39.     ans = mul(ans,inv(add(1,-r)));
  40.     return ans%mod;
  41. }
  42.  
  43. int main(){
  44.     ll n;
  45.     cin>>n;
  46.     // cout<<series(1,2,2);
  47.     ll num = n;
  48.     ll bi = 0;
  49.     while(num!=0){
  50.         num/=2;
  51.         bi++;
  52.     }
  53.     ll p = 4;
  54.     ll prev = 27;
  55.     ll ans=0;
  56.     for(int i = 3;i<=bi;i++){
  57.         ll to=0,las;
  58.         if(i==bi)to = n-p+1,las = n;
  59.         else to = 2*p-p,las=2*p-1;
  60.         ll aa = binpow(2,mul(to,i));
  61.         // cout<<aa<<" "<<prev*aa<<" s\n";
  62.         ans = mul(prev,aa);
  63.         ll a = inv(binpow(2,i));
  64.         ll r = a;
  65.         ll fir = add(p,-mul(las,inv(binpow(2,mul(to,i)))));
  66.         ll cur = 1;
  67.         ll bb = mul(aa,inv(add(binpow(2,i),-1)));
  68.         if(to>=1){
  69.             cur = add(fir,series(a,r,to-1));
  70.             cur = mul(cur,bb);
  71.         }
  72.         ans += (cur);
  73.         ans%=mod;
  74.         p*=2;
  75.         prev=ans;
  76.     }
  77.     cout<<ans;
  78.     return 0;
  79. }
  80.  
  81.  
Success #stdin #stdout 0s 5492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
308459039
https://ideone.com/i5oS23
language:
C++14 (gcc 8.3)
created:
2 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!