API tools faq
paste
Advertisement
BaoJIaoPisu

Untitled

BaoJIaoPisu
Feb 15th, 2023
1,729
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 15.59 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using ld = long double;
  7. using ull = unsigned long long;
  8.  
  9. using pii = pair<int, int>;
  10. using pll = pair<ll, ll>;
  11. using pld = pair<ld, ld>;
  12.  
  13. #define fi first
  14. #define se second
  15. #define left BAO
  16. #define right ANH
  17. #define pb push_back
  18. #define pf push_front
  19. #define mp make_pair
  20. #define ins insert
  21. #define btpc __builtin_popcount
  22. #define btclz __builtin_clz
  23.  
  24. #define sz(x) (int)(x.size());
  25. #define all(x) x.begin(), x.end()
  26. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  27.  
  28. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  29.  
  30. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  31. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  32. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  33.  
  34. template<class X, class Y>
  35.     bool minimize(X &x, const Y &y) {
  36.         if (x > y)
  37.         {
  38.             x = y;
  39.             return true;
  40.         }
  41.         return false;
  42.     }
  43. template<class X, class Y>
  44.     bool maximize(X &x, const Y &y) {
  45.         if (x < y)
  46.         {
  47.             x = y;
  48.             return true;
  49.         }
  50.         return false;
  51.     }
  52.  
  53. const int MOD = 1e9 + 7; //998244353
  54.  
  55. template<class X, class Y>
  56.     void add(X &x, const Y &y) {
  57.         x = (x + y);
  58.         if(x >= MOD) x -= MOD;
  59.     }
  60.  
  61. template<class X, class Y>
  62.     void sub(X &x, const Y &y) {
  63.         x = (x - y);
  64.         if(x < 0) x += MOD;
  65.     }
  66.  
  67. /* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/
  68.  
  69. const ll INF = 1e9;
  70. const int N = 1e5 + 10;
  71.  
  72. const int base = 1000000000;
  73. const int base_digits = 9;
  74. struct BigNum {
  75.     vector<int> a;
  76.     int sign;
  77.     /*<arpa>*/
  78.     int size() {
  79.         if (a.empty())return 0;
  80.         int ans = (a.size() - 1) * base_digits;
  81.         int ca = a.back();
  82.         while (ca)
  83.             ans++, ca /= 10;
  84.         return ans;
  85.     }
  86.     BigNum operator ^(const BigNum &v) {
  87.         BigNum ans = 1, a = *this, b = v;
  88.         while (!b.isZero()) {
  89.             if (b % 2)
  90.                 ans *= a;
  91.             a *= a, b /= 2;
  92.         }
  93.         return ans;
  94.     }
  95.     string to_string() {
  96.         stringstream ss;
  97.         ss << *this;
  98.         string s;
  99.         ss >> s;
  100.         return s;
  101.     }
  102.     int sumof() {
  103.         string s = to_string();
  104.         int ans = 0;
  105.         for (auto c : s)  ans += c - '0';
  106.         return ans;
  107.     }
  108.     /*</arpa>*/
  109.     BigNum() :
  110.         sign(1) {
  111.     }
  112.  
  113.     BigNum(long long v) {
  114.         *this = v;
  115.     }
  116.  
  117.     BigNum(const string &s) {
  118.         read(s);
  119.     }
  120.  
  121.     void operator=(const BigNum &v) {
  122.         sign = v.sign;
  123.         a = v.a;
  124.     }
  125.  
  126.     void operator=(long long v) {
  127.         sign = 1;
  128.         a.clear();
  129.         if (v < 0)
  130.             sign = -1, v = -v;
  131.         for (; v > 0; v = v / base)
  132.             a.push_back(v % base);
  133.     }
  134.  
  135.     BigNum operator+(const BigNum &v) const {
  136.         if (sign == v.sign) {
  137.             BigNum res = v;
  138.  
  139.             for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
  140.                 if (i == (int) res.a.size())
  141.                     res.a.push_back(0);
  142.                 res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
  143.                 carry = res.a[i] >= base;
  144.                 if (carry)
  145.                     res.a[i] -= base;
  146.             }
  147.             return res;
  148.         }
  149.         return *this - (-v);
  150.     }
  151.  
  152.     BigNum operator-(const BigNum &v) const {
  153.         if (sign == v.sign) {
  154.             if (abs() >= v.abs()) {
  155.                 BigNum res = *this;
  156.                 for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
  157.                     res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
  158.                     carry = res.a[i] < 0;
  159.                     if (carry)
  160.                         res.a[i] += base;
  161.                 }
  162.                 res.trim();
  163.                 return res;
  164.             }
  165.             return -(v - *this);
  166.         }
  167.         return *this + (-v);
  168.     }
  169.  
  170.     void operator*=(int v) {
  171.         if (v < 0)
  172.             sign = -sign, v = -v;
  173.         for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
  174.             if (i == (int) a.size())
  175.                 a.push_back(0);
  176.             long long cur = a[i] * (long long) v + carry;
  177.             carry = (int) (cur / base);
  178.             a[i] = (int) (cur % base);
  179.             //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  180.         }
  181.         trim();
  182.     }
  183.  
  184.     BigNum operator*(int v) const {
  185.         BigNum res = *this;
  186.         res *= v;
  187.         return res;
  188.     }
  189.  
  190.  
  191.     friend pair<BigNum, BigNum> divmod(const BigNum &a1, const BigNum &b1) {
  192.         int norm = base / (b1.a.back() + 1);
  193.         BigNum a = a1.abs() * norm;
  194.         BigNum b = b1.abs() * norm;
  195.         BigNum q, r;
  196.         q.a.resize(a.a.size());
  197.  
  198.         for (int i = a.a.size() - 1; i >= 0; i--) {
  199.             r *= base;
  200.             r += a.a[i];
  201.             int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  202.             int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  203.             int d = ((long long) base * s1 + s2) / b.a.back();
  204.             r -= b * d;
  205.             while (r < 0)
  206.                 r += b, --d;
  207.             q.a[i] = d;
  208.         }
  209.  
  210.         q.sign = a1.sign * b1.sign;
  211.         r.sign = a1.sign;
  212.         q.trim();
  213.         r.trim();
  214.         return make_pair(q, r / norm);
  215.     }
  216.  
  217.     BigNum operator/(const BigNum &v) const {
  218.         return divmod(*this, v).first;
  219.     }
  220.  
  221.     BigNum operator%(const BigNum &v) const {
  222.         return divmod(*this, v).second;
  223.     }
  224.  
  225.     void operator/=(int v) {
  226.         if (v < 0)
  227.             sign = -sign, v = -v;
  228.         for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
  229.             long long cur = a[i] + rem * (long long) base;
  230.             a[i] = (int) (cur / v);
  231.             rem = (int) (cur % v);
  232.         }
  233.         trim();
  234.     }
  235.  
  236.     BigNum operator/(int v) const {
  237.         BigNum res = *this;
  238.         res /= v;
  239.         return res;
  240.     }
  241.  
  242.     int operator%(int v) const {
  243.         if (v < 0)
  244.             v = -v;
  245.         int m = 0;
  246.         for (int i = a.size() - 1; i >= 0; --i)
  247.             m = (a[i] + m * (long long) base) % v;
  248.         return m * sign;
  249.     }
  250.  
  251.     void operator+=(const BigNum &v) {
  252.         *this = *this + v;
  253.     }
  254.     void operator-=(const BigNum &v) {
  255.         *this = *this - v;
  256.     }
  257.     void operator*=(const BigNum &v) {
  258.         *this = *this * v;
  259.     }
  260.     void operator/=(const BigNum &v) {
  261.         *this = *this / v;
  262.     }
  263.  
  264.     bool operator<(const BigNum &v) const {
  265.         if (sign != v.sign)
  266.             return sign < v.sign;
  267.         if (a.size() != v.a.size())
  268.             return a.size() * sign < v.a.size() * v.sign;
  269.         for (int i = a.size() - 1; i >= 0; i--)
  270.             if (a[i] != v.a[i])
  271.                 return a[i] * sign < v.a[i] * sign;
  272.         return false;
  273.     }
  274.  
  275.     bool operator>(const BigNum &v) const {
  276.         return v < *this;
  277.     }
  278.     bool operator<=(const BigNum &v) const {
  279.         return !(v < *this);
  280.     }
  281.     bool operator>=(const BigNum &v) const {
  282.         return !(*this < v);
  283.     }
  284.     bool operator==(const BigNum &v) const {
  285.         return !(*this < v) && !(v < *this);
  286.     }
  287.     bool operator!=(const BigNum &v) const {
  288.         return *this < v || v < *this;
  289.     }
  290.  
  291.     void trim() {
  292.         while (!a.empty() && !a.back())
  293.             a.pop_back();
  294.         if (a.empty())
  295.             sign = 1;
  296.     }
  297.  
  298.     bool isZero() const {
  299.         return a.empty() || (a.size() == 1 && !a[0]);
  300.     }
  301.  
  302.     BigNum operator-() const {
  303.         BigNum res = *this;
  304.         res.sign = -sign;
  305.         return res;
  306.     }
  307.  
  308.     BigNum abs() const {
  309.         BigNum res = *this;
  310.         res.sign *= res.sign;
  311.         return res;
  312.     }
  313.  
  314.     long long longValue() const {
  315.         long long res = 0;
  316.         for (int i = a.size() - 1; i >= 0; i--)
  317.             res = res * base + a[i];
  318.         return res * sign;
  319.     }
  320.  
  321.     friend BigNum gcd(const BigNum &a, const BigNum &b) {
  322.         return b.isZero() ? a : gcd(b, a % b);
  323.     }
  324.     friend BigNum lcm(const BigNum &a, const BigNum &b) {
  325.         return a / gcd(a, b) * b;
  326.     }
  327.  
  328.     void read(const string &s) {
  329.         sign = 1;
  330.         a.clear();
  331.         int pos = 0;
  332.         while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
  333.             if (s[pos] == '-')
  334.                 sign = -sign;
  335.             ++pos;
  336.         }
  337.         for (int i = s.size() - 1; i >= pos; i -= base_digits) {
  338.             int x = 0;
  339.             for (int j = max(pos, i - base_digits + 1); j <= i; j++)
  340.                 x = x * 10 + s[j] - '0';
  341.             a.push_back(x);
  342.         }
  343.         trim();
  344.     }
  345.  
  346.     friend istream& operator>>(istream &stream, BigNum &v) {
  347.         string s;
  348.         stream >> s;
  349.         v.read(s);
  350.         return stream;
  351.     }
  352.  
  353.     friend ostream& operator<<(ostream &stream, const BigNum &v) {
  354.         if (v.sign == -1)
  355.             stream << '-';
  356.         stream << (v.a.empty() ? 0 : v.a.back());
  357.         for (int i = (int) v.a.size() - 2; i >= 0; --i)
  358.             stream << setw(base_digits) << setfill('0') << v.a[i];
  359.         return stream;
  360.     }
  361.  
  362.     static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
  363.         vector<long long> p(max(old_digits, new_digits) + 1);
  364.         p[0] = 1;
  365.         for (int i = 1; i < (int) p.size(); i++)
  366.             p[i] = p[i - 1] * 10;
  367.         vector<int> res;
  368.         long long cur = 0;
  369.         int cur_digits = 0;
  370.         for (int i = 0; i < (int) a.size(); i++) {
  371.             cur += a[i] * p[cur_digits];
  372.             cur_digits += old_digits;
  373.             while (cur_digits >= new_digits) {
  374.                 res.push_back((int)(cur % p[new_digits]));
  375.                 cur /= p[new_digits];
  376.                 cur_digits -= new_digits;
  377.             }
  378.         }
  379.         res.push_back((int) cur);
  380.         while (!res.empty() && !res.back())
  381.             res.pop_back();
  382.         return res;
  383.     }
  384.  
  385.     typedef vector<long long> vll;
  386.  
  387.     static vll karatsubaMultiply(const vll &a, const vll &b) {
  388.         int n = a.size();
  389.         vll res(n + n);
  390.         if (n <= 32) {
  391.             for (int i = 0; i < n; i++)
  392.                 for (int j = 0; j < n; j++)
  393.                     res[i + j] += a[i] * b[j];
  394.             return res;
  395.         }
  396.  
  397.         int k = n >> 1;
  398.         vll a1(a.begin(), a.begin() + k);
  399.         vll a2(a.begin() + k, a.end());
  400.         vll b1(b.begin(), b.begin() + k);
  401.         vll b2(b.begin() + k, b.end());
  402.  
  403.         vll a1b1 = karatsubaMultiply(a1, b1);
  404.         vll a2b2 = karatsubaMultiply(a2, b2);
  405.  
  406.         for (int i = 0; i < k; i++)
  407.             a2[i] += a1[i];
  408.         for (int i = 0; i < k; i++)
  409.             b2[i] += b1[i];
  410.  
  411.         vll r = karatsubaMultiply(a2, b2);
  412.         for (int i = 0; i < (int) a1b1.size(); i++)
  413.             r[i] -= a1b1[i];
  414.         for (int i = 0; i < (int) a2b2.size(); i++)
  415.             r[i] -= a2b2[i];
  416.  
  417.         for (int i = 0; i < (int) r.size(); i++)
  418.             res[i + k] += r[i];
  419.         for (int i = 0; i < (int) a1b1.size(); i++)
  420.             res[i] += a1b1[i];
  421.         for (int i = 0; i < (int) a2b2.size(); i++)
  422.             res[i + n] += a2b2[i];
  423.         return res;
  424.     }
  425.  
  426.     BigNum operator*(const BigNum &v) const {
  427.         vector<int> a6 = convert_base(this->a, base_digits, 6);
  428.         vector<int> b6 = convert_base(v.a, base_digits, 6);
  429.         vll a(a6.begin(), a6.end());
  430.         vll b(b6.begin(), b6.end());
  431.         while (a.size() < b.size())
  432.             a.push_back(0);
  433.         while (b.size() < a.size())
  434.             b.push_back(0);
  435.         while (a.size() & (a.size() - 1))
  436.             a.push_back(0), b.push_back(0);
  437.         vll c = karatsubaMultiply(a, b);
  438.         BigNum res;
  439.         res.sign = sign * v.sign;
  440.         for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  441.             long long cur = c[i] + carry;
  442.             res.a.push_back((int) (cur % 1000000));
  443.             carry = (int) (cur / 1000000);
  444.         }
  445.         res.a = convert_base(res.a, 6, base_digits);
  446.         res.trim();
  447.         return res;
  448.     }
  449. };
  450.  
  451. const int LOG = 666;
  452. int fa[LOG + 2], fb[LOG + 2], fc[LOG + 2], fd[LOG + 2];
  453. BigNum f[LOG + 2][2][2][2][2], dp[LOG + 2][2][2][2][2], pw[LOG + 2];
  454.  
  455. BigNum calc(int index, int a, int b, int c, int d) {
  456.     if(index == 0) return 1;
  457.     if(dp[index][a][b][c][d] != -1) return dp[index][a][b][c][d];
  458.     BigNum res = 0;
  459.  
  460.     for(int x = 0; x < 2; x++) {
  461.         for(int y = 0; y < 2; y++) {
  462.             if(!a && x < fa[index - 1]) continue;
  463.             if(!b && x > fb[index - 1]) continue;
  464.             if(!c && y < fc[index - 1]) continue;
  465.             if(!d && y > fd[index - 1]) continue;
  466.            
  467.             int na = (a || x > fa[index - 1]);
  468.             int nb = (b || x < fb[index - 1]);
  469.             int nc = (c || y > fc[index - 1]);
  470.             int nd = (d || y < fd[index - 1]);
  471.             res += calc(index - 1, na, nb, nc, nd);
  472.         }
  473.     }
  474.  
  475.     dp[index][a][b][c][d] = res;
  476.     return res;
  477. }
  478.  
  479. void BaoJiaoPisu() {
  480.     BigNum a, b, c, d; cin >> a >> b >> c >> d;
  481.     BigNum num = (b - a + 1) * (d - c + 1);
  482.     num = (num + 1) / 2;
  483.  
  484.     for(int i = 0; i <= LOG; i++) {
  485.         for(int x = 0; x < 2; x++) {
  486.             for(int y = 0; y < 2; y++) {
  487.                 for(int z = 0; z < 2; z++) {
  488.                     for(int t = 0; t < 2; t++) {
  489.                         f[i][x][y][z][t] = 0;
  490.                         dp[i][x][y][z][t] = -1;
  491.                     }
  492.                 }
  493.             }
  494.         }
  495.     }
  496.  
  497.     for(int i = 0; i <= LOG; i++) {
  498.         fa[i] = (a % 2); a /= 2;
  499.         fb[i] = (b % 2); b /= 2;
  500.         fc[i] = (c % 2); c /= 2;
  501.         fd[i] = (d % 2); d /= 2;
  502.     }
  503.    
  504.     f[LOG][0][0][0][0] = 1;
  505.  
  506.     pw[0] = 1;
  507.     BigNum ans = 0;
  508.     for(int i = 1; i <= LOG; i++) pw[i] = pw[i - 1] * 2;
  509.     for(int i = LOG; i > 0; i--) {
  510.         BigNum one = 0, zero = 0;
  511.         bool larger = false;
  512.         for(int a = 0; a < 2; a++) {
  513.             for(int b = 0; b < 2; b++) {
  514.                 for(int c = 0; c < 2; c++) {
  515.                     for(int d = 0; d < 2; d++) {
  516.                         if(f[i][a][b][c][d] == 0) continue;
  517.                         for(int x = 0; x < 2; x++) {
  518.                             for(int y = 0; y < 2; y++) {
  519.                                 if(larger) continue;
  520.                                 if(!a && x < fa[i - 1]) continue;
  521.                                 if(!b && x > fb[i - 1]) continue;
  522.                                 if(!c && y < fc[i - 1]) continue;
  523.                                 if(!d && y > fd[i - 1]) continue;
  524.  
  525.                                 int na = (a || x > fa[i - 1]);
  526.                                 int nb = (b || x < fb[i - 1]);
  527.                                 int nc = (c || y > fc[i - 1]);
  528.                                 int nd = (d || y < fd[i - 1]);
  529.  
  530.                                 if(x == y) zero += f[i][a][b][c][d] * calc(i - 1, na, nb, nc, nd);
  531.                                 larger = (zero >= num);
  532.                             }
  533.                         }
  534.                     }
  535.                 }
  536.             }
  537.         }
  538.  
  539.         auto add = [&](int bit) -> void {
  540.             for(int a = 0; a < 2; a++) {
  541.                 for(int b = 0; b < 2; b++) {
  542.                     for(int c = 0; c < 2; c++) {
  543.                         for(int d = 0; d < 2; d++) {
  544.                             if(f[i][a][b][c][d] == 0) continue;
  545.                             for(int x = 0; x < 2; x++) {
  546.                                 for(int y = 0; y < 2; y++) {
  547.                                     if((x ^ y) != bit) continue;
  548.                                     if(!a && x < fa[i - 1]) continue;
  549.                                     if(!b && x > fb[i - 1]) continue;
  550.                                     if(!c && y < fc[i - 1]) continue;
  551.                                     if(!d && y > fd[i - 1]) continue;
  552.  
  553.                                     int na = (a || x > fa[i - 1]);
  554.                                     int nb = (b || x < fb[i - 1]);
  555.                                     int nc = (c || y > fc[i - 1]);
  556.                                     int nd = (d || y < fd[i - 1]);
  557.  
  558.                                     f[i - 1][na][nb][nc][nd] += f[i][a][b][c][d];
  559.                                 }
  560.                             }
  561.                         }
  562.                     }
  563.                 }
  564.             }
  565.         };
  566.  
  567.         if(num > zero) {
  568.             num -= zero; ans += pw[i - 1];
  569.             add(1);
  570.         } else add(0);
  571.     }
  572.  
  573.     cout << ans << '\n';
  574. }
  575.  
  576. int main()
  577. {
  578.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  579.     #ifndef ONLINE_JUDGE
  580.     freopen("input.txt", "r", stdin);
  581.     freopen("output.txt", "w", stdout);
  582.     #else
  583.     //online
  584.     #endif
  585.  
  586.     int tc = 1, ddd = 0;
  587.     cin >> tc;
  588.     while(tc--) {
  589.         //ddd++;
  590.         //cout << "Case #" << ddd << ": ";
  591.         BaoJiaoPisu();
  592.     }
  593. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!