fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. using namespace __gnu_pbds;
  5. #define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
  6. #define ll long long
  7. #define ld long double
  8. #define int long long
  9. #define endl "\n"
  10. #define yes cout<<"YES"<<endl;
  11. #define no cout<<"NO"<<endl;
  12. #define pb push_back
  13. //#pragma GCC optimize("O3,unroll-loops")
  14. //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  15. using namespace std;
  16. const int MOD = 1e9 + 7;
  17. //const int MOD = 998244353  ;
  18. const int N = 1e5 + 5;
  19. const ll INF = 1e18;
  20. const ll MIN = -1e18;
  21. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
  22.  
  23. long long binpow(long long a, long long k){
  24.     long long res = 1;
  25.     while (k){
  26.         if (k % 2)
  27.             res = (res * a)%MOD;
  28.         a = (a*a)%MOD ;
  29.         k/=2 ;
  30.     }
  31.     return res ;
  32. }
  33.  
  34.  
  35. void solve() {
  36.     ll l,r;cin>>l>>r;
  37.     function<int(int)> work=[&](int md)->int{
  38.         int dp[66][66][2];
  39.         memset(dp,0ll,sizeof(dp));
  40.         ll msb=log2(md);
  41.         dp[msb][1][1]=1ll;
  42.         for(int i=0;i<msb;i++){
  43.             dp[i][1][0]=1ll;
  44.         }
  45.         for(int bit=msb-1;bit>=0;bit--){
  46.             //1er case: flag false
  47.                 //1.1:bit 0
  48.                 for(int nb=1;nb<=64;nb++){
  49.                     dp[bit][nb][0]+=dp[bit+1][nb][0];
  50.                 }
  51.                 //1.2: bit 1
  52.                 for(int nb=1;nb<64;nb++){
  53.                     dp[bit][nb+1][0]+=dp[bit+1][nb][0];
  54.                 }
  55.             //2nd case : flag true
  56.                 //2.1: true -> true
  57.                 if(md & (1ll<<bit)){
  58.                     for(int nb=1;nb<64;nb++){
  59.                         dp[bit][nb+1][1]+=dp[bit+1][nb][1];
  60.                     }
  61.                 }
  62.                 else{
  63.                     for(int nb=1;nb<=64;nb++){
  64.                         dp[bit][nb][1]+=dp[bit+1][nb][1];
  65.                     }
  66.                 }
  67.                 //2.2 : true -> false
  68.                 if(md & (1ll<<bit)){
  69.                     for(int nb=1;nb<64;nb++){
  70.                         dp[bit][nb][0]+=dp[bit+1][nb][1];
  71.                     }
  72.                 }
  73.         }
  74.         ll ans=0;
  75.         for(int nb=1;nb<=64;nb++){
  76.             for(int flag=0;flag<=1;flag++){
  77.                 ll count=(md-binpow(2,nb)+1+MOD)%MOD;
  78.                 count=(count*dp[0][nb][flag])%MOD;
  79.                 ans=(ans+count)%MOD;
  80.             }
  81.         }
  82.         return (ans* binpow(2,MOD-2))%MOD;
  83.     };
  84.     cout<<(work(r)-work(l-1)+MOD)%MOD<<endl;
  85. }
  86.  
  87. signed main() {
  88.     FAST;
  89.     auto begin = std::chrono::high_resolution_clock::now();
  90.     freopen("or.in", "r", stdin);
  91. #ifndef ONLINE_JUDGE
  92.     freopen("input.txt", "r", stdin);
  93.     freopen("output.txt", "w", stdout);
  94. #endif
  95.     ll t = 1;
  96.     cin >> t;
  97.     while (t--) solve();
  98. #ifndef ONLINE_JUDGE
  99.     auto end = std::chrono::high_resolution_clock::now();
  100.     cout << setprecision(4) << fixed;
  101.     cout << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count()
  102.          << " seconds" << endl;
  103. #endif
  104. }
  105.  
  106.  
  107.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-656655097
https://ideone.com/WyRhg4
language:
C++14 (clang 8.0)
created:
2 days 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!