fork download
copy 
  1. // In the name of Allah.
  2. // We're nothing and you're everything.
  3. // Ya Ali!
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. /*
  11.   ######################################################################
  12.   #######################   THE   BIG   INT   ##########################
  13. */
  14. const int base = 1000000000;
  15. const int base_digits = 9;
  16. struct bigint {
  17.     vector<int> a;
  18.     int sign;
  19.  
  20.     int size(){
  21.         if(a.empty()) return 0;
  22.         int ans = (a.size()-1)*base_digits;
  23.         int ca = a.back();
  24.         while(ca) ans++, ca /= 10;
  25.         return ans;
  26.     }
  27.  
  28.     bigint() : sign(1) {}
  29.     bigint(long long v) { *this = v; }
  30.     bigint(const string &s) { read(s); }
  31.  
  32.     void operator=(const bigint &v){
  33.         sign = v.sign; a = v.a;
  34.     }
  35.  
  36.     void operator=(long long v){
  37.         sign = 1; a.clear();
  38.         if(v < 0) sign = -1, v = -v;
  39.         for(; v > 0; v = v / base) a.push_back((int)(v % base));
  40.     }
  41.  
  42.     bigint operator+(const bigint &v) const {
  43.         if(sign == v.sign){
  44.             bigint res = v;
  45.             for(int i = 0, carry = 0; i < (int)max(a.size(), v.a.size()) || carry; ++i){
  46.                 if(i == (int)res.a.size()) res.a.push_back(0);
  47.                 res.a[i] += carry + (i < (int)a.size() ? a[i] : 0);
  48.                 carry = res.a[i] >= base;
  49.                 if(carry) res.a[i] -= base;
  50.             }
  51.             return res;
  52.         }
  53.         return *this - (-v);
  54.     }
  55.  
  56.     bigint operator-(const bigint &v) const {
  57.         if(sign == v.sign){
  58.             if(abs() >= v.abs()){
  59.                 bigint res = *this;
  60.                 for(int i = 0, carry = 0; i < (int)v.a.size() || carry; ++i){
  61.                     res.a[i] -= carry + (i < (int)v.a.size() ? v.a[i] : 0);
  62.                     carry = res.a[i] < 0;
  63.                     if(carry) res.a[i] += base;
  64.                 }
  65.                 res.trim();
  66.                 return res;
  67.             }
  68.             return -(v - *this);
  69.         }
  70.         return *this + (-v);
  71.     }
  72.  
  73.     void operator*=(int v){
  74.         if(v < 0) sign = -sign, v = -v;
  75.         for(int i = 0, carry = 0; i < (int)a.size() || carry; ++i){
  76.             if(i == (int)a.size()) a.push_back(0);
  77.             long long cur = a[i] * 1LL * v + carry;
  78.             carry = (int)(cur / base);
  79.             a[i] = (int)(cur % base);
  80.         }
  81.         trim();
  82.     }
  83.  
  84.     bigint operator*(int v) const { bigint res = *this; res *= v; return res; }
  85.  
  86.     void operator*=(long long v){
  87.         if(v < 0) sign = -sign, v = -v;
  88.         if(v > base){
  89.             *this = *this * (v / base) * base + *this * (v % base);
  90.             return;
  91.         }
  92.         for(int i = 0, carry = 0; i < (int)a.size() || carry; ++i){
  93.             if(i == (int)a.size()) a.push_back(0);
  94.             long long cur = a[i] * 1LL * v + carry;
  95.             carry = (int)(cur / base);
  96.             a[i] = (int)(cur % base);
  97.         }
  98.         trim();
  99.     }
  100.  
  101.     bigint operator*(long long v) const { bigint res = *this; res *= v; return res; }
  102.  
  103.     friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1){
  104.         int norm = base / (b1.a.back() + 1);
  105.         bigint a = a1.abs() * norm;
  106.         bigint b = b1.abs() * norm;
  107.         bigint q, r;
  108.         q.a.resize(a.a.size());
  109.  
  110.         for(int i = (int)a.a.size() - 1; i >= 0; --i){
  111.             r *= base;
  112.             r += a.a[i];
  113.             int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  114.             int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  115.             int d = ((long long)base * s1 + s2) / b.a.back();
  116.             r -= b * d;
  117.             while(r < 0) r += b, --d;
  118.             q.a[i] = d;
  119.         }
  120.  
  121.         q.sign = a1.sign * b1.sign;
  122.         r.sign = a1.sign;
  123.         q.trim();
  124.         r.trim();
  125.         return make_pair(q, r / norm);
  126.     }
  127.  
  128.     bigint operator/(const bigint &v) const { return divmod(*this, v).first; }
  129.     bigint operator%(const bigint &v) const { return divmod(*this, v).second; }
  130.  
  131.     void operator/=(int v){
  132.         if(v < 0) sign = -sign, v = -v;
  133.         for(int i = (int)a.size() - 1, rem = 0; i >= 0; --i){
  134.             long long cur = a[i] + rem * 1LL * base;
  135.             a[i] = (int)(cur / v);
  136.             rem = (int)(cur % v);
  137.         }
  138.         trim();
  139.     }
  140.  
  141.     bigint operator/(int v) const { bigint res = *this; res /= v; return res; }
  142.  
  143.     int operator%(int v) const {
  144.         if(v < 0) v = -v;
  145.         int m = 0;
  146.         for(int i = (int)a.size() - 1; i >= 0; --i)
  147.             m = (a[i] + m * 1LL * base) % v;
  148.         return m * sign;
  149.     }
  150.  
  151.     void operator+=(const bigint &v){ *this = *this + v; }
  152.     void operator-=(const bigint &v){ *this = *this - v; }
  153.     void operator*=(const bigint &v){ *this = *this * v; }
  154.     void operator/=(const bigint &v){ *this = *this / v; }
  155.     void operator%=(const bigint &v){ *this = *this % v; }
  156.  
  157.     bool operator<(const bigint &v) const {
  158.         if(sign != v.sign) return sign < v.sign;
  159.         if(a.size() != v.a.size()) return a.size() * sign < v.a.size() * v.sign;
  160.         for(int i = (int)a.size() - 1; i >= 0; --i)
  161.             if(a[i] != v.a[i]) return a[i] * sign < v.a[i] * sign;
  162.         return false;
  163.     }
  164.     bool operator>(const bigint &v) const { return v < *this; }
  165.     bool operator<=(const bigint &v) const { return !(v < *this); }
  166.     bool operator>=(const bigint &v) const { return !(*this < v); }
  167.     bool operator==(const bigint &v) const { return !(*this < v) && !(v < *this); }
  168.     bool operator!=(const bigint &v) const { return *this < v || v < *this; }
  169.  
  170.     void trim(){
  171.         while(!a.empty() && !a.back()) a.pop_back();
  172.         if(a.empty()) sign = 1;
  173.     }
  174.  
  175.     bool isZero() const { return a.empty() || (a.size() == 1 && !a[0]); }
  176.  
  177.     bigint operator-() const { bigint res = *this; res.sign = -sign; return res; }
  178.     bigint abs() const { bigint res = *this; res.sign *= res.sign; return res; }
  179.  
  180.     long long longValue() const {
  181.         long long res = 0;
  182.         for(int i = (int)a.size()-1; i >= 0; --i) res = res * base + a[i];
  183.         return res * sign;
  184.     }
  185.  
  186.     friend bigint gcd(const bigint &a, const bigint &b){ return b.isZero() ? a : gcd(b, a % b); }
  187.     friend bigint lcm(const bigint &a, const bigint &b){ return a / gcd(a,b) * b; }
  188.  
  189.     void read(const string &s){
  190.         sign = 1; a.clear();
  191.         int pos = 0;
  192.         while(pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+')){
  193.             if(s[pos] == '-') sign = -sign;
  194.             ++pos;
  195.         }
  196.         for(int i = (int)s.size() - 1; i >= pos; i -= base_digits){
  197.             int x = 0;
  198.             for(int j = max(pos, i - base_digits + 1); j <= i; ++j)
  199.                 x = x * 10 + s[j] - '0';
  200.             a.push_back(x);
  201.         }
  202.         trim();
  203.     }
  204.  
  205.     friend istream& operator>>(istream &stream, bigint &v){
  206.         string s; stream >> s; v.read(s); return stream;
  207.     }
  208.  
  209.     friend ostream& operator<<(ostream &stream, const bigint &v){
  210.         if(v.sign == -1) stream << '-';
  211.         stream << (v.a.empty() ? 0 : v.a.back());
  212.         for(int i = (int)v.a.size() - 2; i >= 0; --i)
  213.             stream << setw(base_digits) << setfill('0') << v.a[i];
  214.         return stream;
  215.     }
  216.  
  217.     static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits){
  218.         vector<long long> p(max(old_digits, new_digits) + 1);
  219.         p[0] = 1;
  220.         for(int i = 1; i < (int)p.size(); ++i) p[i] = p[i-1] * 10;
  221.         vector<int> res;
  222.         long long cur = 0; int cur_digits = 0;
  223.         for(int i = 0; i < (int)a.size(); ++i){
  224.             cur += a[i] * p[cur_digits];
  225.             cur_digits += old_digits;
  226.             while(cur_digits >= new_digits){
  227.                 res.push_back((int)(cur % p[new_digits]));
  228.                 cur /= p[new_digits];
  229.                 cur_digits -= new_digits;
  230.             }
  231.         }
  232.         res.push_back((int)cur);
  233.         while(!res.empty() && !res.back()) res.pop_back();
  234.         return res;
  235.     }
  236.  
  237.     typedef vector<long long> vll;
  238.  
  239.     static vll karatsubaMultiply(const vll &a, const vll &b){
  240.         int n = a.size();
  241.         vll res(n + n);
  242.         if(n <= 32){
  243.             for(int i = 0; i < n; ++i)
  244.                 for(int j = 0; j < n; ++j)
  245.                     res[i + j] += a[i] * b[j];
  246.             return res;
  247.         }
  248.         int k = n >> 1;
  249.         vll a1(a.begin(), a.begin() + k);
  250.         vll a2(a.begin() + k, a.end());
  251.         vll b1(b.begin(), b.begin() + k);
  252.         vll b2(b.begin() + k, b.end());
  253.  
  254.         vll a1b1 = karatsubaMultiply(a1, b1);
  255.         vll a2b2 = karatsubaMultiply(a2, b2);
  256.  
  257.         for(int i = 0; i < k; ++i) a2[i] += a1[i];
  258.         for(int i = 0; i < k; ++i) b2[i] += b1[i];
  259.  
  260.         vll r = karatsubaMultiply(a2, b2);
  261.         for(int i = 0; i < (int)a1b1.size(); ++i) r[i] -= a1b1[i];
  262.         for(int i = 0; i < (int)a2b2.size(); ++i) r[i] -= a2b2[i];
  263.  
  264.         for(int i = 0; i < (int)r.size(); ++i) res[i + k] += r[i];
  265.         for(int i = 0; i < (int)a1b1.size(); ++i) res[i] += a1b1[i];
  266.         for(int i = 0; i < (int)a2b2.size(); ++i) res[i + n] += a2b2[i];
  267.         return res;
  268.     }
  269.  
  270.     bigint operator*(const bigint &v) const {
  271.         vector<int> a6 = convert_base(this->a, base_digits, 6);
  272.         vector<int> b6 = convert_base(v.a, base_digits, 6);
  273.         vll A(a6.begin(), a6.end()), B(b6.begin(), b6.end());
  274.         while(A.size() < B.size()) A.push_back(0);
  275.         while(B.size() < A.size()) B.push_back(0);
  276.         while(A.size() & (A.size() - 1)) A.push_back(0), B.push_back(0);
  277.         vll c = karatsubaMultiply(A, B);
  278.         bigint res;
  279.         res.sign = sign * v.sign;
  280.         for(int i = 0, carry = 0; i < (int)c.size(); ++i){
  281.             long long cur = c[i] + carry;
  282.             res.a.push_back((int)(cur % 1000000));
  283.             carry = (int)(cur / 1000000);
  284.         }
  285.         res.a = convert_base(res.a, 6, base_digits);
  286.         res.trim();
  287.         return res;
  288.     }
  289. };
  290.  
  291. // --- algorithm part ---
  292. const long long MOD = 1000000007LL;
  293.  
  294. // ones_upto(M, pow2) = count of integers x in [0, M] with bit corresponding to pow2 equal 1
  295. bigint ones_upto(const bigint &M, const bigint &pow2){
  296.     bigint zero = 0;
  297.     if(M < zero) return zero;
  298.  
  299.     bigint cycle = pow2 * 2;
  300.     bigint total = M;
  301.     total += bigint(1);
  302.  
  303.     bigint full = total / cycle;
  304.     bigint res = full * pow2;
  305.  
  306.     bigint rem = total % cycle;
  307.     if(rem > pow2) res += (rem - pow2);
  308.     return res;
  309. }
  310.  
  311. // convert bigint to modulo (0..MOD-1) using operator%(int)
  312. long long mod_bigint(const bigint &x, long long mod){
  313.     int m = x % (int)mod; // mod fits in int (1e9+7)
  314.     if(m < 0) m += (int)mod;
  315.     return (long long)m;
  316. }
  317.  
  318. // compute S using your bigint
  319. long long compute_S(const bigint &L, const bigint &R){
  320.     bigint one = 1;
  321.     bigint n = R - L + one;
  322.  
  323.     long long ans = 0;
  324.     long long pow2mod = 1;
  325.  
  326.     bigint pow2 = 1;   // 2^0
  327.  
  328.     for(; pow2 <= R; pow2 *= 2){
  329.         bigint c = ones_upto(R, pow2) - ones_upto(L - one, pow2);
  330.         bigint z = n - c;
  331.  
  332.         long long cmod = mod_bigint(c, MOD);
  333.         long long zmod = mod_bigint(z, MOD);
  334.  
  335.         long long c2 = (cmod * cmod) % MOD;
  336.         long long z2 = (zmod * zmod) % MOD;
  337.  
  338.         long long cntodd = 4;
  339.         cntodd = (cntodd * cmod) % MOD;
  340.         cntodd = (cntodd * zmod) % MOD;
  341.         cntodd = (cntodd * ((c2 + z2) % MOD)) % MOD;
  342.  
  343.         ans = (ans + cntodd * pow2mod) % MOD;
  344.         pow2mod = (pow2mod * 2) % MOD;
  345.     }
  346.  
  347.     if(ans < 0) ans += MOD;
  348.     return ans;
  349. }
  350.  
  351. int main(){
  352.     ios::sync_with_stdio(false);
  353.     cin.tie(nullptr);
  354.  
  355.     string Ls, Rs;
  356.     if(!(cin >> Ls >> Rs)) return 0;
  357.     bigint L(Ls), R(Rs);
  358.     cout << compute_S(L, R) << '\n';
  359.     return 0;
  360. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5JV9Y2
language:
C++14 (gcc 8.3)
created:
8 hours 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!