fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. class BigInt {
  6. private:
  7.     static const int BASE = 1000000000;
  8.     static const int BASE_DIGITS = 9;
  9.     bool is_negative;
  10.  
  11.     void trim() {
  12.         while (!digits.empty() && digits.back() == 0)
  13.             digits.pop_back();
  14.         if (digits.empty())
  15.             is_negative = false;
  16.     }
  17.  
  18.     static BigInt abs(const BigInt& n) {
  19.         BigInt result = n;
  20.         result.is_negative = false;
  21.         return result;
  22.     }
  23.  
  24. public:
  25.     std::vector<int> digits;
  26.  
  27.     BigInt() : is_negative(false) {}
  28.  
  29.     BigInt(long long value) {
  30.         if (value < 0) {
  31.             is_negative = true;
  32.             value = -value;
  33.         } else {
  34.             is_negative = false;
  35.         }
  36.  
  37.         while (value) {
  38.             digits.push_back(value % BASE);
  39.             value /= BASE;
  40.         }
  41.     }
  42.  
  43.     BigInt(const std::string& str) {
  44.         is_negative = false;
  45.         digits.clear();
  46.         int start = 0;
  47.  
  48.         if (!str.empty() && str[0] == '-') {
  49.             is_negative = true;
  50.             start = 1;
  51.         }
  52.  
  53.         for (int i = str.size() - 1; i >= start; i -= BASE_DIGITS) {
  54.             int end = std::max(start, i - BASE_DIGITS + 1);
  55.             int part = std::stoi(str.substr(end, i - end + 1));
  56.             digits.push_back(part);
  57.         }
  58.  
  59.         trim();
  60.     }
  61.  
  62.     friend std::ostream& operator<<(std::ostream& out, const BigInt& n) {
  63.         if (n.is_negative && !n.digits.empty())
  64.             out << "-";
  65.         if (n.digits.empty()) {
  66.             out << "0";
  67.         } else {
  68.             out << n.digits.back();
  69.             for (int i = n.digits.size() - 2; i >= 0; i--)
  70.                 out << std::setw(BASE_DIGITS) << std::setfill('0') << n.digits[i];
  71.         }
  72.         return out;
  73.     }
  74.  
  75.     bool operator==(const BigInt& other) const {
  76.         return is_negative == other.is_negative && digits == other.digits;
  77.     }
  78.  
  79.     bool operator<(const BigInt& other) const {
  80.         if (is_negative != other.is_negative)
  81.             return is_negative;
  82.  
  83.         if (digits.size() != other.digits.size())
  84.             return digits.size() < other.digits.size();
  85.  
  86.         for (int i = digits.size() - 1; i >= 0; i--) {
  87.             if (digits[i] != other.digits[i])
  88.                 return digits[i] < other.digits[i];
  89.         }
  90.  
  91.         return false;
  92.     }
  93.  
  94.     bool operator<=(const BigInt& other) const {
  95.         return *this < other || *this == other;
  96.     }
  97.  
  98.     BigInt operator+(const BigInt& other) const {
  99.         if (is_negative != other.is_negative) {
  100.             return *this - (-other);
  101.         }
  102.  
  103.         BigInt result;
  104.         result.is_negative = is_negative;
  105.  
  106.         int carry = 0;
  107.         for (size_t i = 0; i < std::max(digits.size(), other.digits.size()) || carry; ++i) {
  108.             if (i == result.digits.size())
  109.                 result.digits.push_back(0);
  110.  
  111.             result.digits[i] = carry + (i < digits.size() ? digits[i] : 0) +
  112.                                (i < other.digits.size() ? other.digits[i] : 0);
  113.             carry = result.digits[i] >= BASE;
  114.             if (carry)
  115.                 result.digits[i] -= BASE;
  116.         }
  117.  
  118.         return result;
  119.     }
  120.  
  121.     BigInt operator-(const BigInt& other) const {
  122.         if (is_negative != other.is_negative) {
  123.             return *this + (-other);
  124.         }
  125.  
  126.         if (abs(*this) < abs(other)) {
  127.             return -(other - *this);
  128.         }
  129.  
  130.         BigInt result;
  131.         result.is_negative = is_negative;
  132.  
  133.         int carry = 0;
  134.         for (size_t i = 0; i < digits.size() || carry; ++i) {
  135.             result.digits.push_back(digits[i] - carry - (i < other.digits.size() ? other.digits[i] : 0));
  136.             carry = result.digits.back() < 0;
  137.             if (carry)
  138.                 result.digits.back() += BASE;
  139.         }
  140.  
  141.         result.trim();
  142.         return result;
  143.     }
  144.  
  145.     BigInt operator*(const BigInt& other) const {
  146.         BigInt result;
  147.         result.digits.resize(digits.size() + other.digits.size());
  148.         result.is_negative = is_negative != other.is_negative;
  149.  
  150.         for (size_t i = 0; i < digits.size(); ++i) {
  151.             long long carry = 0;
  152.             for (size_t j = 0; j < other.digits.size() || carry; ++j) {
  153.                 long long current = result.digits[i + j] +
  154.                                     1LL * digits[i] * (j < other.digits.size() ? other.digits[j] : 0) + carry;
  155.                 carry = current / BASE;
  156.                 result.digits[i + j] = current % BASE;
  157.             }
  158.         }
  159.  
  160.         result.trim();
  161.         return result;
  162.     }
  163.  
  164.     void operator /= (long long x) {
  165.         for (int i = (int) digits.size() - 1; i >= 0; i--) {
  166.             if (i) digits[i - 1] += (digits[i] % x) * BASE;
  167.             digits[i] /= x;
  168.         }
  169.         while (!digits.empty() && digits.back() == 0)
  170.             digits.pop_back();
  171.     }
  172.  
  173.     BigInt operator / (long long x) {
  174.         BigInt n(*this);
  175.         n /= x;
  176.         return n;
  177.     }
  178.  
  179.     BigInt operator-() const {
  180.         BigInt result = *this;
  181.         result.is_negative = !result.is_negative;
  182.         return result;
  183.     }
  184.  
  185.     bool is_even() {
  186.         return digits.empty() || digits[0] % 2 == 0;
  187.     }
  188. };
  189.  
  190. void simplify(BigInt &a, BigInt &b) {
  191.     if (a == 0) {
  192.         b = 1;
  193.         return;
  194.     }
  195.     if (b == 0) {
  196.         a = 1;
  197.         return;
  198.     }
  199.     if (a.is_even() && b.is_even()) {
  200.         a = a / 2;
  201.         b = b / 2;
  202.         simplify(a, b);
  203.         return;
  204.     }
  205.     if (a.is_even()) {
  206.         a = a / 2;
  207.         simplify(a, b);
  208.         a = a * 2;
  209.         return;
  210.     }
  211.     if (b.is_even()) {
  212.         b = b / 2;
  213.         simplify(a, b);
  214.         b = b * 2;
  215.         return;
  216.     }
  217.     if (b < a) {
  218.         simplify(b, a);
  219.         return;
  220.     }
  221.     b = b - a;
  222.     simplify(a, b);
  223.     b = b + a;
  224. }
  225.  
  226. const int N = 101;
  227.  
  228. BigInt f[N];
  229. BigInt c[N][N];
  230. BigInt t[N];
  231.  
  232. void precalc() {
  233.     f[0] = 1;
  234.  
  235.     for (int i = 1; i < N; ++i) {
  236.         f[i] = f[i - 1] * i;
  237.     }
  238.  
  239.     for (int i = 0; i < N; ++i) {
  240.         c[i][0] = c[i][i] = 1;
  241.         for (int j = 1; j < i; ++j) {
  242.             c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
  243.         }
  244.     }
  245. }
  246.  
  247. BigInt binpow(const BigInt& x, int y) {
  248.     if (y == 0) {
  249.         return 1;
  250.     }
  251.     if (y & 1) {
  252.         return binpow(x, y - 1) * x;
  253.     }
  254.     BigInt z = binpow(x, y / 2);
  255.     return z * z;
  256. }
  257.  
  258. int32_t main() {
  259.     precalc();
  260.  
  261.     int n, m, k;
  262.  
  263.     while (cin >> n >> m >> k) {
  264.         if (n == m && m == k && k == 0) {
  265.             break;
  266.         }
  267.         if (k > min(n, m)) {
  268.             cout << "0/1\n";
  269.             continue;
  270.         }
  271.         if (m == 0) {
  272.             cout << (k == m) << '/' << 1 << '\n';
  273.             continue;
  274.         }
  275.  
  276.         t[0] = 0;
  277.         for (int i = 1; i <= k; ++i) {
  278.             t[i] = binpow(i, m);
  279.             for (int j = 0; j < i; ++j) {
  280.                 t[i] = t[i] - c[i][j] * t[j];
  281.             }
  282.         }
  283.  
  284.         BigInt p = c[n][k] * t[k];
  285.         BigInt q = binpow(n, m);
  286.  
  287.         simplify(p, q);
  288.  
  289.         cout << p << '/' << q << '\n';
  290.     }
  291. }
  292.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zAPAth
language:
C++ (gcc 8.3)
created:
1 day 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!