fork download
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. //#define pb push_back
  12. #define pb emplace_back
  13. #define fi first
  14. #define se second
  15. #define sz(s) (int)s.size()
  16. #define all(s) (s).begin(), (s).end()
  17. #define ms(a,x) memset(a, x, sizeof (a))
  18. #define cn continue
  19. #define re exit(0)
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28. typedef vector<pii> vpii;
  29. typedef vector<pll> vpll;
  30.  
  31. const int mod=1e9+7;
  32. const int maxn=3e5+15;
  33. const int maxm=4*maxn+15;
  34. const ll inf=1e17;
  35.  
  36. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  37. ll ran(ll l, ll r)
  38. {
  39. return uniform_int_distribution<ll> (l, r)(rng);
  40. }
  41.  
  42. inline void rf(){
  43. ios_base::sync_with_stdio(false);
  44. cin.tie(nullptr); cout.tie(nullptr);
  45. if(fopen(file".inp","r")){
  46. freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
  47. }
  48. }
  49.  
  50. template<typename T> inline void add(T &x, const T &y)
  51. {
  52. x+=y;
  53. if(x>=mod) x-=mod;
  54. if(x<0) x+=mod;
  55. }
  56.  
  57. template<typename T> inline bool maxi(T &a, T b)
  58. {
  59. if(a>=b) return 0;
  60. a=b; return 1;
  61. }
  62.  
  63. template<typename T> inline bool mini(T &a, T b)
  64. {
  65. if(a<=b) return 0;
  66. a=b; return 1;
  67. }
  68.  
  69. int n;
  70. string s, curxor, lim;
  71. ll f[70][2][2];
  72.  
  73. string dec(ll x)
  74. {
  75. if(x==0) return "0";
  76. string ans="";
  77. while(x) ans+=char(x%10+48), x/=10;
  78. reverse(all(ans));
  79. return ans;
  80. }
  81.  
  82. string bin(ll x)
  83. {
  84. if(x==0) return "0";
  85. string ans="";
  86. while(x) ans+=char(x%2+48), x/=2;
  87. while(ans.size()<60) ans+='0';
  88. reverse(all(ans));
  89. return ans;
  90. }
  91.  
  92. ll cal(int id, bool smaller1, bool smaller2)
  93. {
  94. ll &cur=f[id][smaller1][smaller2];
  95. if(id==n) return cur=1;
  96. if(cur+1) return cur;
  97. cur=0;
  98. int i=curxor[id]-'0';
  99. if(smaller1 || i<=(s[id]-'0')) if(smaller2 || (0<=lim[id]-'0'))
  100. {
  101. cur+=cal(id+1, smaller1 || i<(s[id]-'0'), smaller2 || (0<lim[id]-'0'));
  102. }
  103. i=1-i;
  104. if(smaller1 || i<=(s[id]-'0')) if(smaller2 || (1<=lim[id]-'0'))
  105. {
  106. cur+=cal(id+1, smaller1 || i<(s[id]-'0'), smaller2 || (1<lim[id]-'0'));
  107. }
  108. return cur;
  109. }
  110.  
  111. signed main()
  112. {
  113. rf();
  114. ll x, l, r, limit; cin>>x>>l>>r>>limit;
  115. curxor=bin(x); lim=bin(limit);
  116. ms(f, -1); s=bin(r); n=sz(s);
  117. ll ans=cal(0, 0, 0);
  118. ms(f, -1); s=bin(l-1); n=sz(s);
  119. ans-=cal(0, 0, 0);
  120. cout<<ans;
  121. re;
  122. }
Success #stdin #stdout 0.01s 5324KB
stdin
66 32 67 22
stdout
4