Advertisement
jeff69

Untitled

Sep 16th, 2017
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define popCnt(x) (__builtin_popcountll(x))
  4. typedef long long Long;
  5.  
  6. // base and base_digits must be consistent
  7. const int base = 1000000000;
  8. const int base_digits = 9;
  9.  
  10. struct BigInt {
  11.   vector<int> z;
  12.   int sign;
  13.  
  14.   BigInt() :
  15.     sign(1) {
  16.   }
  17.  
  18.   BigInt(long long v) {
  19.     *this = v;
  20.   }
  21.  
  22.   BigInt(const string &s) {
  23.     read(s);
  24.   }
  25.  
  26.   BigInt operator=(const BigInt &v) {
  27.     sign = v.sign;
  28.     z = v.z;
  29.     return *this;
  30.   }
  31.  
  32.   void operator=(long long v) {
  33.     sign = 1;
  34.     if (v < 0) sign = -1, v = -v;
  35.     z.clear();
  36.     for (; v > 0; v = v / base)
  37.       z.push_back(v % base);
  38.   }
  39.  
  40.   BigInt operator+(const BigInt &v) const {
  41.     if (sign == v.sign) {
  42.       BigInt res = v;
  43.  
  44.       for (int i = 0, carry = 0; i < (int) max(z.size(), v.z.size()) || carry;
  45.         ++i) {
  46.         if (i == (int) res.z.size()) res.z.push_back(0);
  47.         res.z[i] += carry + (i < (int) z.size() ? z[i] : 0);
  48.         carry = res.z[i] >= base;
  49.         if (carry) res.z[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.z.size() || carry; ++i) {
  61.           res.z[i] -= carry + (i < (int) v.z.size() ? v.z[i] : 0);
  62.           carry = res.z[i] < 0;
  63.           if (carry) res.z[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) z.size() || carry; ++i) {
  76.       if (i == (int) z.size()) z.push_back(0);
  77.       long long cur = z[i] * (long long) v + carry;
  78.       carry = (int) (cur / base);
  79.       z[i] = (int) (cur % base);
  80.       //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  81.     }
  82.     trim();
  83.   }
  84.  
  85.   BigInt operator*(int v) const {
  86.     BigInt res = *this;
  87.     res *= v;
  88.     return res;
  89.   }
  90.  
  91.   friend pair<BigInt, BigInt> divmod(const BigInt &a1, const BigInt &b1) {
  92.     int norm = base / (b1.z.back() + 1);
  93.     BigInt a = a1.abs() * norm;
  94.     BigInt b = b1.abs() * norm;
  95.     BigInt q, r;
  96.     q.z.resize(a.z.size());
  97.  
  98.     for (int i = a.z.size() - 1; i >= 0; i--) {
  99.       r *= base;
  100.       r += a.z[i];
  101.       int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
  102.       int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
  103.       int d = ((long long) s1 * base + s2) / b.z.back();
  104.       r -= b * d;
  105.       while (r < 0)
  106.         r += b, --d;
  107.       q.z[i] = d;
  108.     }
  109.  
  110.     q.sign = a1.sign * b1.sign;
  111.     r.sign = a1.sign;
  112.     q.trim();
  113.     r.trim();
  114.     return make_pair(q, r / norm);
  115.   }
  116.  
  117.   friend BigInt sqrt(const BigInt &a1) {
  118.     BigInt a = a1;
  119.     while (a.z.empty() || a.z.size() % 2 == 1)
  120.       a.z.push_back(0);
  121.  
  122.     int n = a.z.size();
  123.  
  124.     int firstDigit = (int) sqrt((double) a.z[n - 1] * base + a.z[n - 2]);
  125.     int norm = base / (firstDigit + 1);
  126.     a *= norm;
  127.     a *= norm;
  128.     while (a.z.empty() || a.z.size() % 2 == 1)
  129.       a.z.push_back(0);
  130.  
  131.     BigInt r = (long long) a.z[n - 1] * base + a.z[n - 2];
  132.     firstDigit = (int) sqrt((double) a.z[n - 1] * base + a.z[n - 2]);
  133.     int q = firstDigit;
  134.     BigInt res;
  135.  
  136.     for (int j = n / 2 - 1; j >= 0; j--) {
  137.       for (;; --q) {
  138.         BigInt r1 = (r - (res * 2 * base + q) * q) * base * base
  139.           + (j > 0 ? (long long) a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
  140.         if (r1 >= 0) {
  141.           r = r1;
  142.           break;
  143.         }
  144.       }
  145.       res *= base;
  146.       res += q;
  147.  
  148.       if (j > 0) {
  149.         int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
  150.         int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
  151.         int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
  152.         q = ((long long) d1 * base * base + (long long) d2 * base + d3)
  153.           / (firstDigit * 2);
  154.       }
  155.     }
  156.  
  157.     res.trim();
  158.     return res / norm;
  159.   }
  160.  
  161.   BigInt operator/(const BigInt &v) const {
  162.     return divmod(*this, v).first;
  163.   }
  164.  
  165.   BigInt operator%(const BigInt &v) const {
  166.     return divmod(*this, v).second;
  167.   }
  168.  
  169.   void operator/=(int v) {
  170.     if (v < 0) sign = -sign, v = -v;
  171.     for (int i = (int) z.size() - 1, rem = 0; i >= 0; --i) {
  172.       long long cur = z[i] + rem * (long long) base;
  173.       z[i] = (int) (cur / v);
  174.       rem = (int) (cur % v);
  175.     }
  176.     trim();
  177.   }
  178.  
  179.   BigInt operator/(int v) const {
  180.     BigInt res = *this;
  181.     res /= v;
  182.     return res;
  183.   }
  184.  
  185.   int operator%(int v) const {
  186.     if (v < 0) v = -v;
  187.     int m = 0;
  188.     for (int i = z.size() - 1; i >= 0; --i)
  189.       m = (z[i] + m * (long long) base) % v;
  190.     return m * sign;
  191.   }
  192.  
  193.   void operator+=(const BigInt &v) {
  194.     *this = *this + v;
  195.   }
  196.   void operator-=(const BigInt &v) {
  197.     *this = *this - v;
  198.   }
  199.   void operator*=(const BigInt &v) {
  200.     *this = *this * v;
  201.   }
  202.   void operator/=(const BigInt &v) {
  203.     *this = *this / v;
  204.   }
  205.  
  206.   bool operator<(const BigInt &v) const {
  207.     if (sign != v.sign) return sign < v.sign;
  208.     if (z.size() != v.z.size()) return z.size() * sign < v.z.size() * v.sign;
  209.     for (int i = z.size() - 1; i >= 0; i--)
  210.       if (z[i] != v.z[i]) return z[i] * sign < v.z[i] * sign;
  211.     return false;
  212.   }
  213.  
  214.   bool operator>(const BigInt &v) const {
  215.     return v < *this;
  216.   }
  217.   bool operator<=(const BigInt &v) const {
  218.     return !(v < *this);
  219.   }
  220.   bool operator>=(const BigInt &v) const {
  221.     return !(*this < v);
  222.   }
  223.   bool operator==(const BigInt &v) const {
  224.     return !(*this < v) && !(v < *this);
  225.   }
  226.   bool operator!=(const BigInt &v) const {
  227.     return *this < v || v < *this;
  228.   }
  229.  
  230.   void trim() {
  231.     while (!z.empty() && z.back() == 0)
  232.       z.pop_back();
  233.     if (z.empty()) sign = 1;
  234.   }
  235.  
  236.   bool isZero() const {
  237.     return z.empty() || (z.size() == 1 && !z[0]);
  238.   }
  239.  
  240.   BigInt operator-() const {
  241.     BigInt res = *this;
  242.     res.sign = -sign;
  243.     return res;
  244.   }
  245.  
  246.   BigInt abs() const {
  247.     BigInt res = *this;
  248.     res.sign *= res.sign;
  249.     return res;
  250.   }
  251.  
  252.   long long longValue() const {
  253.     long long res = 0;
  254.     for (int i = z.size() - 1; i >= 0; i--)
  255.       res = res * base + z[i];
  256.     return res * sign;
  257.   }
  258.  
  259.   friend BigInt gcd(const BigInt &a, const BigInt &b) {
  260.     return b.isZero() ? a : gcd(b, a % b);
  261.   }
  262.   friend BigInt lcm(const BigInt &a, const BigInt &b) {
  263.     return a / gcd(a, b) * b;
  264.   }
  265.  
  266.   void read(const string &s) {
  267.     sign = 1;
  268.     z.clear();
  269.     int pos = 0;
  270.     while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
  271.       if (s[pos] == '-') sign = -sign;
  272.       ++pos;
  273.     }
  274.     for (int i = s.size() - 1; i >= pos; i -= base_digits) {
  275.       int x = 0;
  276.       for (int j = max(pos, i - base_digits + 1); j <= i; j++)
  277.         x = x * 10 + s[j] - '0';
  278.       z.push_back(x);
  279.     }
  280.     trim();
  281.   }
  282.  
  283.   friend istream& operator>>(istream &stream, BigInt &v) {
  284.     string s;
  285.     stream >> s;
  286.     v.read(s);
  287.     return stream;
  288.   }
  289.  
  290.   friend ostream& operator<<(ostream &stream, const BigInt &v) {
  291.     if (v.sign == -1) stream << '-';
  292.     stream << (v.z.empty() ? 0 : v.z.back());
  293.     for (int i = (int) v.z.size() - 2; i >= 0; --i)
  294.       stream << setw(base_digits) << setfill('0') << v.z[i];
  295.     return stream;
  296.   }
  297.  
  298.   static vector<int> convert_base(const vector<int> &a, int old_digits,
  299.     int new_digits) {
  300.     vector<long long> p(max(old_digits, new_digits) + 1);
  301.     p[0] = 1;
  302.     for (int i = 1; i < (int) p.size(); i++)
  303.       p[i] = p[i - 1] * 10;
  304.     vector<int> res;
  305.     long long cur = 0;
  306.     int cur_digits = 0;
  307.     for (int i = 0; i < (int) a.size(); i++) {
  308.       cur += a[i] * p[cur_digits];
  309.       cur_digits += old_digits;
  310.       while (cur_digits >= new_digits) {
  311.         res.push_back(int(cur % p[new_digits]));
  312.         cur /= p[new_digits];
  313.         cur_digits -= new_digits;
  314.       }
  315.     }
  316.     res.push_back((int) cur);
  317.     while (!res.empty() && res.back() == 0)
  318.       res.pop_back();
  319.     return res;
  320.   }
  321.  
  322.   typedef vector<long long> vll;
  323.  
  324.   static vll karatsubaMultiply(const vll &a, const vll &b) {
  325.     int n = a.size();
  326.     vll res(n + n);
  327.     if (n <= 32) {
  328.       for (int i = 0; i < n; i++)
  329.         for (int j = 0; j < n; j++)
  330.           res[i + j] += a[i] * b[j];
  331.       return res;
  332.     }
  333.  
  334.     int k = n >> 1;
  335.     vll a1(a.begin(), a.begin() + k);
  336.     vll a2(a.begin() + k, a.end());
  337.     vll b1(b.begin(), b.begin() + k);
  338.     vll b2(b.begin() + k, b.end());
  339.  
  340.     vll a1b1 = karatsubaMultiply(a1, b1);
  341.     vll a2b2 = karatsubaMultiply(a2, b2);
  342.  
  343.     for (int i = 0; i < k; i++)
  344.       a2[i] += a1[i];
  345.     for (int i = 0; i < k; i++)
  346.       b2[i] += b1[i];
  347.  
  348.     vll r = karatsubaMultiply(a2, b2);
  349.     for (int i = 0; i < (int) a1b1.size(); i++)
  350.       r[i] -= a1b1[i];
  351.     for (int i = 0; i < (int) a2b2.size(); i++)
  352.       r[i] -= a2b2[i];
  353.  
  354.     for (int i = 0; i < (int) r.size(); i++)
  355.       res[i + k] += r[i];
  356.     for (int i = 0; i < (int) a1b1.size(); i++)
  357.       res[i] += a1b1[i];
  358.     for (int i = 0; i < (int) a2b2.size(); i++)
  359.       res[i + n] += a2b2[i];
  360.     return res;
  361.   }
  362.  
  363.   BigInt operator*(const BigInt &v) const {
  364.     vector<int> a6 = convert_base(this->z, base_digits, 6);
  365.     vector<int> b6 = convert_base(v.z, base_digits, 6);
  366.     vll a(a6.begin(), a6.end());
  367.     vll b(b6.begin(), b6.end());
  368.     while (a.size() < b.size())
  369.       a.push_back(0);
  370.     while (b.size() < a.size())
  371.       b.push_back(0);
  372.     while (a.size() & (a.size() - 1))
  373.       a.push_back(0), b.push_back(0);
  374.     vll c = karatsubaMultiply(a, b);
  375.     BigInt res;
  376.     res.sign = sign * v.sign;
  377.     for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  378.       long long cur = c[i] + carry;
  379.       res.z.push_back((int) (cur % 1000000));
  380.       carry = (int) (cur / 1000000);
  381.     }
  382.     res.z = convert_base(res.z, 6, base_digits);
  383.     res.trim();
  384.     return res;
  385.   }
  386. };
  387.  
  388. const int MX = 102;
  389. BigInt dp[MX][MX];
  390.  
  391. BigInt ncr[MX][MX];
  392. BigInt C(int n, int r) {
  393.   if (r < 0 || n < r || r > n) return 0;
  394.   if (r == 0) return 1;
  395.   auto& res = ncr[n][r];
  396.  
  397.   if (res != -1) return res;
  398.   res = C(n - 1, r - 1) + C(n - 1, r);
  399.   return res;
  400. }
  401. BigInt fact[MX];
  402. BigInt solve(int n, int k) {
  403.   if (k < 0) return 0;
  404.   if (n == 0) return k == 0;
  405.  
  406.   auto& res = dp[n][k];
  407.   if (res != -1) return res;
  408.  
  409.   res = solve(n - 1, k - 1);
  410.  
  411.   for (int i = 2; i <= n; ++i) {
  412.     res += solve(n - i, k) * C(n - 1, i - 1) * fact[i - 1];
  413.   }
  414.  
  415.   return res;
  416. }
  417.  
  418. int main() {
  419.   fact[0] = 1;
  420.   for (int i = 1; i < MX; ++i) {
  421.     fact[i] = fact[i - 1] * i;
  422.   }
  423.   for (int i = 0; i < MX; ++i) {
  424.     for (int j = 0; j < MX; ++j) {
  425.       ncr[i][j] = -1;
  426.       dp[i][j] = -1;
  427.     }
  428.   }
  429.   int n, k;
  430.   cin >> k >> n;
  431.  
  432.   auto x = solve(n, k);
  433.   auto y = fact[n];
  434.  
  435.   if (x == 0) {
  436.     cout << 0;
  437.     return 0;
  438.   }
  439.  
  440.   auto g = gcd(x, y);
  441.  
  442.   x /= g;
  443.   y /= g;
  444.  
  445.   cout << x << "/" << y;
  446.  
  447. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement