fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <set>
  5. #include <map>
  6. #include <queue>
  7. #include <stack>
  8. #include <algorithm>
  9. #include <unordered_map>
  10. #include <unordered_set>
  11. #include <climits>
  12. #include <iomanip>
  13. #include <cstdio>
  14. #include<fstream>
  15. #define ll    long long int
  16. #define MOD 1000000007
  17. #define inf  20000000000000
  18. #define eps  0.0000000000001
  19. using namespace std ; 
  20.  
  21.  
  22. ll  n ;
  23.  
  24. ll arr[61] ;  
  25.  
  26. int main()
  27. {
  28.  // ios::sync_with_stdio(false);cin.tie(0) ;cout.tie(0) ;
  29.  
  30.   cin>>n ;  
  31.  
  32.  
  33.  for(ll i   = 1  ;  i <=  n ; ++i)
  34.  {
  35.     for(ll  j  = 0  ;  j <= 60  ;++j)
  36.     {
  37.          if( ( (1LL << j) & i  ) >  0 )
  38.            arr[j]++  ;  
  39.     }
  40.  }
  41.  
  42. ll maxbit = 0  ;
  43. for(ll j  = 60 ;  j  >= 0  ; --j)
  44. {
  45.     if(arr[j] >  0  )
  46.       {
  47.           maxbit  =  j  ;  
  48.           break ;   
  49.       }
  50. }
  51.  
  52. //cout<<"maxbit "<<maxbit<<"\n" ;
  53.  
  54.  
  55.  
  56.  ll carry =  0   ;
  57.  
  58.  vector<ll>ans ;   
  59.  
  60.  for(ll  i = 0  ;  i  <=  maxbit ; ++i)
  61.  {
  62.     ll noOfPresent =  arr[i]  ; 
  63.     ll noOfAbsent =  n   -noOfPresent  ;  
  64.  
  65.  
  66.     //for present number
  67.     ll sum =  (noOfPresent * n)     ;
  68.     //for absent numbers
  69.     sum =  (sum +  (noOfAbsent * noOfPresent)) ;     
  70.  
  71.     sum =   (sum + carry);  
  72.  
  73.  
  74.  
  75.    if(sum % 2 == 0 )
  76.    {
  77.     carry = sum/2 ;   
  78.     ans.push_back(0) ;
  79.     }
  80.     else
  81.     {
  82.     carry = sum/2 ;   
  83.     ans.push_back(1) ;
  84.     } 
  85.  
  86.    // cout<<carry<<" "<<sum<<"\n";
  87.  }
  88.  
  89.  
  90.  
  91.  
  92.  
  93. vector<ll>car ;   
  94. ll cur = 0   ;
  95. while(carry > 0)
  96. {
  97.  
  98.    if( ( carry & 1 )  > 0 )
  99.       car.push_back(1)  ;
  100.    else
  101.       car.push_back(0)  ;  
  102.  
  103.    cur++ ; 
  104.    carry  = (carry >> 1 ); 
  105. }
  106.  
  107.  
  108. // for(auto y  : car)
  109. //   cout<<y  ;  
  110. // cout<<"\n\n";
  111.  
  112.  
  113. for(auto j   : car)
  114.    ans.push_back(j) ;  
  115.  
  116.  
  117.  reverse(ans.begin()   ,  ans.end() ) ;  
  118.  
  119.  
  120.  
  121.  
  122.  ll fans  = 0  ;   
  123.  
  124.  
  125.    cur =  1 ;   
  126.  
  127.  
  128.  
  129.   for(ll    j  =  ans.size()   - 1  ;  j  >=  0 ; --j  )
  130.   {
  131.  
  132.  
  133.              if(ans[j] == 1)
  134.              {
  135.                  fans  =  (fans +  cur)%MOD ;  
  136.              }
  137.  
  138.              cur = (cur * 2) % MOD ;  
  139.   }
  140.  
  141.  
  142.  
  143. cout<< (fans %  MOD) ; 
  144.  
  145.  
  146.  
  147.  
  148.  
  149.   return 0 ;
  150.  
  151. } 
  152.  
  153.  
  154.  
  155.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TlC9J0
language:
C++14 (gcc 8.3)
created:
4 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!