fork download
copy 
  1. /*                  ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠀⣰⣿⣿⣿⡟⠁⠀⣠⣾⣿⣿⣿⣿⡿⠟⣿⣿⣿⣿⣿⡿⠿⠛⠛⠉⠉⠙⠛⠻⠿⣿⣿⣿⣿⣿⣿⣶⣤⣀⡀⠀⠀⠀⠹⣿⣿
  2.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⢰⣿⣿⣿⡏⠀⠀⣼⣿⣿⣿⣿⠟⠉⣠⣾⣿⠿⠛⣉⣀⣤⣤⣴⣶⣶⣶⣶⣶⣤⣀⡀⠉⠙⠻⣿⣿⣿⣿⣿⣿⣄⡀⠀⠀⠈⠛
  3.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠈⣿⣿⣿⡇⠀⣼⣿⣿⣿⡿⢃⣤⣾⣿⣫⣵⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣶⣤⡤⠄
  4.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠀⠘⣿⣿⡇⢰⣿⣿⣿⡿⠾⠿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣦⠀⠀⢻⣿⣿⣿⣿⣧⡀⠀⠀⠀
  5.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣼⣦⡘⣿⣧⡿⢻⠙⠉⠀⢀⣀⣴⣿⣿⡿⠉⠀⠀⠉⠉⠙⠻⣿⣎⢿⣿⣿⣿⣿⣧⠙⣿⣟⢿⣧⡀⠀⢻⣿⣿⣿⣿⣿⣦⡀⠀
  6.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⡻⢋⣾⠚⠋⠀⠀⠀⠀⠀⣼⣿⣿⣿⣿⣀⠀⠀⠀⠀⣀⣴⣾⣿⠿⡌⢿⣿⣿⣿⣿⣧⠘⢿⡄⠉⠻⣄⠀⢻⣿⣏⠛⠛⠻⢿⣄
  7.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⢰⣿⠟⠀⠀⠀⠀⠀⠀⠐⠉⠀⢹⣿⣿⣿⣤⣤⣴⣾⣿⣿⣿⠁⠀⠛⠜⣿⣿⣿⣿⣿⣧⠈⢿⡄⢠⠈⠃⠀⠻⣿⣧⡀⠀⠀⣈
  8.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢸⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⡿⠿⠛⢻⣷⣶⣿⣿⡘⣿⣿⠹⣿⣿⠀⠈⢿⣄⢳⣤⡀⠀⠙⠛⠿⣆⠀⠘
  9.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⣾⣿⠀⠀⠀⠀⠀⠀⠀⣼⣿⣿⣿⣿⢻⡿⠛⠉⠉⣀⡀⠠⠄⠀⠀⠙⠿⣇⢹⣿⡇⢻⡟⢸⡀⠈⢿⣮⣿⣿⣶⣦⣄⣀⣀⣀⣀
  10.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣫⣾⣿⡟⠀⠀⠀⠀⠀⠀⠀⢀⠟⢻⡿⠁⠀⢀⡤⠚⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⢰⣿⣿⠈⢁⣿⡇⠀⣾⣿⣿⣿⣿⣿⣿⣿⡿⠟⣉
  11.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣛⣩⠾⠿⠿⠿⢿⡕⢆⠀⠀⠀⠀⠀⠊⠀⠈⠀⣠⠔⣋⣠⣤⣄⣉⣀⡀⠀⠀⠀⠀⠀⢈⣾⣿⣿⡆⣼⣿⠇⠰⣿⣿⣿⣟⠛⢛⣉⣡⣴⣾⣿
  12.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⡿⣄⣧⡀⠀⢠⠀⠑⢤⠴⢋⠁⡾⢻⡿⣿⣿⣯⠛⠛⠲⠤⠀⠀⢠⣾⣿⣿⣿⣿⣿⣿⢠⠄⠈⢻⣿⣿⣆⠘⢿⣿⣿⠛⠉
  13.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣹⣿⢿⡃⣿⣦⡀⠀⠀⠀⠀⠀⢠⠇⣿⣇⢀⣿⣿⡇⠀⠀⠀⠀⣀⣾⣿⣿⣿⣿⣿⣿⠇⠀⡀⢄⠀⠩⠻⢿⣷⡌⠻⢿⣧⠀
  14.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢸⣗⢻⣼⣯⠄⠀⠀⠀⠀⠀⠀⠸⣿⣿⣿⡿⠃⠀⠀⠀⢠⣾⣿⣿⣿⠿⢋⣿⠟⠀⠑⠈⠀⠁⡀⠀⣼⣿⣿⣶⣤⣽⣇
  15.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣼⣿⡥⠙⠟⠄⠀⠀⠀⠀⠀⠀⠀⠀⣉⠩⠔⠀⠀⢀⣼⠿⠟⠋⠁⠀⠀⣸⠏⠀⡀⠄⠠⠁⠌⠀⣰⣿⣿⡿⣱⣷⣿⡻
  16.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣋⣐⣿⢯⡇⠩⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⠉⠁⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠀⣤⠀⠀⢀⣾⣿⣿⣿⠳⠿⣿⣿⡿
  17.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⡇⢀⣶⣿⣿⣿⣿⣿⣶⣤⡤⠄⣠
  18.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡆⠢⠄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠋⠀⠇⠘⠛⣿⣿⣿⣿⡿⢛⣩⣴⣾⣿
  19.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⢀⣔⠂⠈⢑⡇⠿⣿⣿⣿⣷⡘⢿⣿⣿⣿
  20.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡈⠁⠀⠀⠀⠉⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠐⠰⢶⡃⣔⣼⡅⢁⠜⠙⣛⣻⢿⣮⣛⣿⣿
  21.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣤⠀⠛⠿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠔⠀⠀⢀⠀⠀⣳⢻⢸⡼⡦⢁⣴⣾⣿⣿⣧⡻⣿⣿⣿
  22.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⠞⠁⠀⠀⠄⠀⣈⡄⡟⠛⠈⠋⠁⣿⣿⣿⣿⣿⣿⣿⣮⣻⣿
  23.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⢤⡀⣐⠶⠿⠟⠁⢂⣀⠤⠴⠒⠉⣁⡄⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣷⣝
  24.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣁⡠⡐⣄⡇⢰⠂⠉⠉⢀⣀⣤⣴⣶⣿⣿⡧⠀⠀⠐⣀⣈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  25.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣯⣾⣿⡘⣵⠈⡆⠰⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  26.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⢉⣽⣶⣶⣿⡿⣿⣿⣿⡇⡟⡀⡇⠀⣿⣿⣿⣿⣿⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠉
  27.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠛⠁⠀⠔⠛⠛⠉⠉⠁⣰⣿⣿⣿⣿⣃⣇⠠⠀⣽⣿⣿⣿⠃⠀⠀⠙⠛⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⠀⠀
  28.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢁⣤⡾⠃⠀⠀⠀⠀⠀⢰⣿⣿⣿⣿⡿⠛⢻⣿⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠉⠙⠻⠿⣿⣿⣿⡿⠃⠀⠀⠀
  29.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢏⣶⣿⣿⠃⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⠁⠀⠀⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⢻⣥⡀⠀⠀⠀
  30.                     ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢏⣾⣿⣿⡏⠀⠀⠀⠀⠀⢀⣼⣿⣿⣿⣿⣿⠀⠀⠀⣿⣿⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⣿⣿⣿⣷⡀⠀                                                                                                                                                                                                                                                                                                                   */
  31. /* I love CatTuong */
  32. #include <bits/stdc++.h>
  33. #define ll long long
  34. #define ull unsigned long long
  35. #define pb push_back
  36. #define pf push_front
  37. #define pii pair<int,int>
  38. #define fi first
  39. #define se second
  40. #define IN endl
  41. #define CT ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  42. #define BIT(x, i) (((x) >> (i)) & 1)
  43. #define all(x) (x).begin(), (x).end()
  44. #define MASK(i) (1LL << (i))
  45. #define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
  46. using namespace std;
  47. #define int long long
  48. const int INF = numeric_limits<int>::max();
  49. const int nax = (int)(301);
  50. const int mod = 1e9 + 7;
  51. template<class X, class Y>
  52. bool maximize(X& x, const Y y) {
  53.     if (y > x) {x = y; return true;}
  54.     return false;
  55. }
  56. template<class X, class Y>
  57. bool minimize(X& x, const Y y) {
  58.     if (y < x) {x = y; return true;}
  59.     return false;
  60. }
  61.  
  62. const int base = 1000000000;
  63. const int base_digits = 9;
  64. struct bigint {
  65.     vector<int> a;
  66.     int sign;
  67.     /*<arpa>*/
  68.     int size() {
  69.         if (a.empty())return 0;
  70.         int ans = (a.size() - 1) * base_digits;
  71.         int ca = a.back();
  72.         while (ca)
  73.             ans++, ca /= 10;
  74.         return ans;
  75.     }
  76.     bigint operator ^(const bigint &v) {
  77.         bigint ans = 1, a = *this, b = v;
  78.         while (!b.isZero()) {
  79.             if (b % 2)
  80.                 ans *= a;
  81.             a *= a, b /= 2;
  82.         }
  83.         return ans;
  84.     }
  85.     string to_string() {
  86.         stringstream ss;
  87.         ss << *this;
  88.         string s;
  89.         ss >> s;
  90.         return s;
  91.     }
  92.     int sumof() {
  93.         string s = to_string();
  94.         int ans = 0;
  95.         for (auto c : s)  ans += c - '0';
  96.         return ans;
  97.     }
  98.     bigint() :
  99.         sign(1) {
  100.     }
  101.  
  102.     bigint(long long v) {
  103.         *this = v;
  104.     }
  105.  
  106.     bigint(const string &s) {
  107.         read(s);
  108.     }
  109.  
  110.     void operator=(const bigint &v) {
  111.         sign = v.sign;
  112.         a = v.a;
  113.     }
  114.  
  115.     void operator=(long long v) {
  116.         sign = 1;
  117.         a.clear();
  118.         if (v < 0)
  119.             sign = -1, v = -v;
  120.         for (; v > 0; v = v / base)
  121.             a.push_back(v % base);
  122.     }
  123.  
  124.     bigint operator+(const bigint &v) const {
  125.         if (sign == v.sign) {
  126.             bigint res = v;
  127.  
  128.             for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
  129.                 if (i == (int) res.a.size())
  130.                     res.a.push_back(0);
  131.                 res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
  132.                 carry = res.a[i] >= base;
  133.                 if (carry)
  134.                     res.a[i] -= base;
  135.             }
  136.             return res;
  137.         }
  138.         return *this - (-v);
  139.     }
  140.  
  141.     bigint operator-(const bigint &v) const {
  142.         if (sign == v.sign) {
  143.             if (abs() >= v.abs()) {
  144.                 bigint res = *this;
  145.                 for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
  146.                     res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
  147.                     carry = res.a[i] < 0;
  148.                     if (carry)
  149.                         res.a[i] += base;
  150.                 }
  151.                 res.trim();
  152.                 return res;
  153.             }
  154.             return -(v - *this);
  155.         }
  156.         return *this + (-v);
  157.     }
  158.  
  159.     void operator*=(int v) {
  160.         if (v < 0)
  161.             sign = -sign, v = -v;
  162.         for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
  163.             if (i == (int) a.size())
  164.                 a.push_back(0);
  165.             long long cur = a[i] * (long long) v + carry;
  166.             carry = (int) (cur / base);
  167.             a[i] = (int) (cur % base);
  168.         }
  169.         trim();
  170.     }
  171.  
  172.     bigint operator*(int v) const {
  173.         bigint res = *this;
  174.         res *= v;
  175.         return res;
  176.     }
  177.  
  178.  
  179.     friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
  180.         int norm = base / (b1.a.back() + 1);
  181.         bigint a = a1.abs() * norm;
  182.         bigint b = b1.abs() * norm;
  183.         bigint q, r;
  184.         q.a.resize(a.a.size());
  185.  
  186.         for (int i = a.a.size() - 1; i >= 0; i--) {
  187.             r *= base;
  188.             r += a.a[i];
  189.             int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  190.             int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  191.             int d = ((long long) base * s1 + s2) / b.a.back();
  192.             r -= b * d;
  193.             while (r < 0)
  194.                 r += b, --d;
  195.             q.a[i] = d;
  196.         }
  197.  
  198.         q.sign = a1.sign * b1.sign;
  199.         r.sign = a1.sign;
  200.         q.trim();
  201.         r.trim();
  202.         return make_pair(q, r / norm);
  203.     }
  204.  
  205.     bigint operator/(const bigint &v) const {
  206.         return divmod(*this, v).first;
  207.     }
  208.  
  209.     bigint operator%(const bigint &v) const {
  210.         return divmod(*this, v).second;
  211.     }
  212.  
  213.     void operator/=(int v) {
  214.         if (v < 0)
  215.             sign = -sign, v = -v;
  216.         for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
  217.             long long cur = a[i] + rem * (long long) base;
  218.             a[i] = (int) (cur / v);
  219.             rem = (int) (cur % v);
  220.         }
  221.         trim();
  222.     }
  223.  
  224.     bigint operator/(int v) const {
  225.         bigint res = *this;
  226.         res /= v;
  227.         return res;
  228.     }
  229.  
  230.     int operator%(int v) const {
  231.         if (v < 0)
  232.             v = -v;
  233.         int m = 0;
  234.         for (int i = a.size() - 1; i >= 0; --i)
  235.             m = (a[i] + m * (long long) base) % v;
  236.         return m * sign;
  237.     }
  238.  
  239.     void operator+=(const bigint &v) {
  240.         *this = *this + v;
  241.     }
  242.     void operator-=(const bigint &v) {
  243.         *this = *this - v;
  244.     }
  245.     void operator*=(const bigint &v) {
  246.         *this = *this * v;
  247.     }
  248.     void operator/=(const bigint &v) {
  249.         *this = *this / v;
  250.     }
  251.  
  252.     bool operator<(const bigint &v) const {
  253.         if (sign != v.sign)
  254.             return sign < v.sign;
  255.         if (a.size() != v.a.size())
  256.             return a.size() * sign < v.a.size() * v.sign;
  257.         for (int i = a.size() - 1; i >= 0; i--)
  258.             if (a[i] != v.a[i])
  259.                 return a[i] * sign < v.a[i] * sign;
  260.         return false;
  261.     }
  262.  
  263.     bool operator>(const bigint &v) const {
  264.         return v < *this;
  265.     }
  266.     bool operator<=(const bigint &v) const {
  267.         return !(v < *this);
  268.     }
  269.     bool operator>=(const bigint &v) const {
  270.         return !(*this < v);
  271.     }
  272.     bool operator==(const bigint &v) const {
  273.         return !(*this < v) && !(v < *this);
  274.     }
  275.     bool operator!=(const bigint &v) const {
  276.         return *this < v || v < *this;
  277.     }
  278.  
  279.     void trim() {
  280.         while (!a.empty() && !a.back())
  281.             a.pop_back();
  282.         if (a.empty())
  283.             sign = 1;
  284.     }
  285.  
  286.     bool isZero() const {
  287.         return a.empty() || (a.size() == 1 && !a[0]);
  288.     }
  289.  
  290.     bigint operator-() const {
  291.         bigint res = *this;
  292.         res.sign = -sign;
  293.         return res;
  294.     }
  295.  
  296.     bigint abs() const {
  297.         bigint res = *this;
  298.         res.sign *= res.sign;
  299.         return res;
  300.     }
  301.  
  302.     long long longValue() const {
  303.         long long res = 0;
  304.         for (int i = a.size() - 1; i >= 0; i--)
  305.             res = res * base + a[i];
  306.         return res * sign;
  307.     }
  308.  
  309.     friend bigint gcd(const bigint &a, const bigint &b) {
  310.         return b.isZero() ? a : gcd(b, a % b);
  311.     }
  312.     friend bigint lcm(const bigint &a, const bigint &b) {
  313.         return a / gcd(a, b) * b;
  314.     }
  315.  
  316.     void read(const string &s) {
  317.         sign = 1;
  318.         a.clear();
  319.         int pos = 0;
  320.         while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
  321.             if (s[pos] == '-')
  322.                 sign = -sign;
  323.             ++pos;
  324.         }
  325.         for (int i = s.size() - 1; i >= pos; i -= base_digits) {
  326.             int x = 0;
  327.             for (int j = max(pos, i - base_digits + 1); j <= i; j++)
  328.                 x = x * 10 + s[j] - '0';
  329.             a.push_back(x);
  330.         }
  331.         trim();
  332.     }
  333.  
  334.     friend istream& operator>>(istream &stream, bigint &v) {
  335.         string s;
  336.         stream >> s;
  337.         v.read(s);
  338.         return stream;
  339.     }
  340.  
  341.     friend ostream& operator<<(ostream &stream, const bigint &v) {
  342.         if (v.sign == -1)
  343.             stream << '-';
  344.         stream << (v.a.empty() ? 0 : v.a.back());
  345.         for (int i = (int) v.a.size() - 2; i >= 0; --i)
  346.             stream << setw(base_digits) << setfill('0') << v.a[i];
  347.         return stream;
  348.     }
  349.  
  350.     static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
  351.         vector<long long> p(max(old_digits, new_digits) + 1);
  352.         p[0] = 1;
  353.         for (int i = 1; i < (int) p.size(); i++)
  354.             p[i] = p[i - 1] * 10;
  355.         vector<int> res;
  356.         long long cur = 0;
  357.         int cur_digits = 0;
  358.         for (int i = 0; i < (int) a.size(); i++) {
  359.             cur += a[i] * p[cur_digits];
  360.             cur_digits += old_digits;
  361.             while (cur_digits >= new_digits) {
  362.                 res.push_back((int)(cur % p[new_digits]));
  363.                 cur /= p[new_digits];
  364.                 cur_digits -= new_digits;
  365.             }
  366.         }
  367.         res.push_back((int) cur);
  368.         while (!res.empty() && !res.back())
  369.             res.pop_back();
  370.         return res;
  371.     }
  372.  
  373.     typedef vector<long long> vll;
  374.  
  375.     static vll karatsubaMultiply(const vll &a, const vll &b) {
  376.         int n = a.size();
  377.         vll res(n + n);
  378.         if (n <= 32) {
  379.             for (int i = 0; i < n; i++)
  380.                 for (int j = 0; j < n; j++)
  381.                     res[i + j] += a[i] * b[j];
  382.             return res;
  383.         }
  384.  
  385.         int k = n >> 1;
  386.         vll a1(a.begin(), a.begin() + k);
  387.         vll a2(a.begin() + k, a.end());
  388.         vll b1(b.begin(), b.begin() + k);
  389.         vll b2(b.begin() + k, b.end());
  390.  
  391.         vll a1b1 = karatsubaMultiply(a1, b1);
  392.         vll a2b2 = karatsubaMultiply(a2, b2);
  393.  
  394.         for (int i = 0; i < k; i++)
  395.             a2[i] += a1[i];
  396.         for (int i = 0; i < k; i++)
  397.             b2[i] += b1[i];
  398.  
  399.         vll r = karatsubaMultiply(a2, b2);
  400.         for (int i = 0; i < (int) a1b1.size(); i++)
  401.             r[i] -= a1b1[i];
  402.         for (int i = 0; i < (int) a2b2.size(); i++)
  403.             r[i] -= a2b2[i];
  404.  
  405.         for (int i = 0; i < (int) r.size(); i++)
  406.             res[i + k] += r[i];
  407.         for (int i = 0; i < (int) a1b1.size(); i++)
  408.             res[i] += a1b1[i];
  409.         for (int i = 0; i < (int) a2b2.size(); i++)
  410.             res[i + n] += a2b2[i];
  411.         return res;
  412.     }
  413.  
  414.     bigint operator*(const bigint &v) const {
  415.         vector<int> a6 = convert_base(this->a, base_digits, 6);
  416.         vector<int> b6 = convert_base(v.a, base_digits, 6);
  417.         vll a(a6.begin(), a6.end());
  418.         vll b(b6.begin(), b6.end());
  419.         while (a.size() < b.size())
  420.             a.push_back(0);
  421.         while (b.size() < a.size())
  422.             b.push_back(0);
  423.         while (a.size() & (a.size() - 1))
  424.             a.push_back(0), b.push_back(0);
  425.         vll c = karatsubaMultiply(a, b);
  426.         bigint res;
  427.         res.sign = sign * v.sign;
  428.         for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  429.             long long cur = c[i] + carry;
  430.             res.a.push_back((int) (cur % 1000000));
  431.             carry = (int) (cur / 1000000);
  432.         }
  433.         res.a = convert_base(res.a, 6, base_digits);
  434.         res.trim();
  435.         return res;
  436.     }
  437. };
  438.  
  439. bigint ncr[nax][nax];
  440. int ans[nax], a[nax];
  441. signed main() {
  442.     CT
  443.     ncr[0][0] = 1;
  444.     for (int i = 1; i < nax; ++i) {
  445.         ncr[i][0] = 1;
  446.         for (int j = 1; j <= i; ++j) {
  447.             ncr[i][j] = ncr[i - 1][j] + ncr[i - 1][j - 1];
  448.         }
  449.     }
  450.     int n, k;
  451.     cin >> n >> k;
  452.     bigint s;
  453.     cin >> s;
  454.     int cur = 1;
  455.     for (int i = 1; i <= k; ++i) {
  456.         while (cur <= n) {
  457.             if (s > ncr[n - cur][k - i]) {
  458.                 s -= ncr[n - cur][k - i];
  459.                 cur++;
  460.             } else {
  461.                 ans[i] = cur;
  462.                 cur++;
  463.                 break;
  464.             }
  465.         }
  466.     }
  467.     for (int i = 1; i <= k; ++i) {
  468.         cout << ans[i];
  469.         if (i < k) {
  470.             cout << " ";
  471.         }
  472.     }
  473.     cout << IN;
  474.     for (int i = 1; i <= k; ++i) {
  475.         cin >> a[i];
  476.     }
  477.     bigint ansp = 1;
  478.     cur = 1;
  479.     for (int i = 1; i <= k; ++i) {
  480.         while (cur < a[i]) {
  481.             ansp += ncr[n - cur][k - i];
  482.             cur++;
  483.         }
  484.         cur++;
  485.     }
  486.     cout << ansp << IN;
  487.     return 0;
  488. }
  489.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Sc64zb
language:
C++14 (gcc 8.3)
created:
53 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!