Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2017
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.15 KB | None | 0 0
  1. // Philip_PV
  2.  
  3. #include <fstream>
  4. #include <iostream>
  5. #include <set>
  6. #include <map>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <deque>
  12. #include <stack>
  13. #include <bitset>
  14. #include <functional>
  15. #include <numeric>
  16. #include <utility>
  17. #include <sstream>
  18. #include <iomanip>
  19. #include <cstdio>
  20. #include <cstdlib>
  21. #include <algorithm>
  22. #include <cassert>
  23. #include <ctime>
  24. #include <memory.h>
  25. #include <cmath>
  26.  
  27. using namespace std;
  28.  
  29. typedef long long ll;
  30. typedef unsigned long long ull;
  31. typedef unsigned int uint;
  32.  
  33. typedef pair<double, double> pdd;
  34. typedef pair<int, int> pii;
  35.  
  36. /*
  37. #define x first
  38. #define y second
  39. //*/
  40.  
  41. #ifdef _DEBUG
  42.   #define dbg(x) { cerr << #x << " = " << x << endl; }
  43. #else
  44.   #define dbg(x) ;
  45. #endif
  46.  
  47. #define forn(_i,_n) for (int _i = 0; _i < (int)(_n); ++_i)
  48. #define mp make_pair
  49.  
  50. #define SIZE 200
  51. #define mod 1000000
  52.  
  53. struct bigint {
  54.   int data[SIZE], size;
  55.  
  56.   bigint() { }
  57.  
  58.   inline void zero() {
  59.     memset(data, 0, sizeof(data));
  60.     size = 1;
  61.   }
  62.  
  63.   inline void one() {
  64.     zero();
  65.     data[0] = 1;
  66.   }
  67.  
  68.   void norm() {
  69.     int rem = 0;
  70.     forn (i, size) {
  71.       data[i] += rem;
  72.       rem = data[i] / mod;
  73.       data[i] %= mod;
  74.     }
  75.  
  76.     while (rem) {
  77.       data[size] = rem;
  78.       rem = data[size] / mod;
  79.       data[size] %= mod;
  80.       size++;
  81.     }
  82.   }
  83.  
  84.   int div(int n, bool d) {
  85.     int rem = 0;
  86.     for (int i = size - 1; i >= 0; i--) {
  87.       int v = data[i] + rem * mod;
  88.       rem = v % n;
  89.       if (d) data[i] = v / n;
  90.     }
  91.     while (size > 1 && !data[size - 1]) size--;
  92.     return rem;
  93.   }
  94.  
  95.   void print() {
  96.     while (size > 1 && !data[size - 1]) size--;
  97.     printf("%d", data[size - 1]);
  98.     for (int i = size - 2; i >= 0; i--)
  99.       printf("%06d", data[i]);
  100.   }
  101.  
  102.   inline void mul(int n) {
  103.     forn (i, size)
  104.       data[i] *= n;
  105.     norm();
  106.   }
  107. };
  108.  
  109. void prepare(bigint& a, bigint& b, int n) {
  110.   for (int i = 2; i <= n; i++) {
  111.     bool ok = true;
  112.     for (int j = 2; j < i; j++)
  113.       if (i % j == 0) ok = false;
  114.  
  115.     int t = n, cnt = 0;
  116.     while (t) cnt += (t/=i);
  117.     if (ok)
  118.       while (cnt-- && !a.div(i, false)) {
  119.         a.div(i, true);
  120.         b.div(i, true);
  121.       }
  122.   }
  123. }
  124.  
  125. bigint A[470], B, ansA[470], ansB[470];
  126. vector<int> Q;
  127.  
  128. int main() {
  129.   /*
  130.   cout << 461 << endl;
  131.   forn (i, 462)
  132.     cout << i << endl;
  133.   return 0;
  134.   */
  135.  
  136.   forn (i, 470) A[i].one();
  137.   B.one();
  138.   ansA[0].one(); ansB[0].one();
  139.  
  140.   int t; cin >> t;
  141.   Q.reserve(t);
  142.   forn (i, t) cin >> Q[i];
  143.  
  144.   int _m = 0;
  145.   forn (i, t) _m = max(_m, Q[i]);
  146.  
  147.   for (int n = 1; n <= _m; n++) {
  148.     B.mul(n);
  149.     forn (i, n)
  150.       A[i].mul(n - i);
  151.     A[n] = B;
  152.  
  153.     ansB[n] = B;
  154.     ansA[n].zero();
  155.  
  156.     forn (i, n + 1) {
  157.       forn (j, A[i].size)
  158.         ansA[n].data[j] += A[i].data[j];
  159.       ansA[n].size = max(ansA[n].size, A[i].size);
  160.     }
  161.     ansA[n].norm();
  162.   }
  163.  
  164.   forn (i, t) {
  165.     int n = Q[i];
  166.     prepare(ansA[n], ansB[n], n);
  167.     ansA[n].print();
  168.     if (ansB[n].size == 1 && ansB[n].data[0] == 1);
  169.     else {
  170.       putchar('/');
  171.       ansB[n].print();
  172.     }
  173.     putchar('\n');
  174.   }
  175.   flush(cout);
  176.  
  177.   return 0;
  178. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement