fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <map>
  4. #include <cctype>
  5. #include <cassert>
  6.  
  7. enum {
  8.   BIT = 30,
  9.   CMASK = 1 << BIT,
  10.   BMASK = CMASK - 1,
  11. };
  12.  
  13. class BigInteger {
  14. private:
  15.   int n;
  16.   int *b;
  17. private:
  18.   static bool iszero(BigInteger &n);
  19. public:
  20.   BigInteger();
  21.   BigInteger(const BigInteger &ob);
  22.   BigInteger(const int n);
  23.   ~BigInteger();
  24.   BigInteger operator=(BigInteger n);
  25.   BigInteger operator=(int n);
  26.   friend bool operator==(BigInteger const &a, BigInteger const &b);
  27.   friend bool operator==(BigInteger const &a, int const b);
  28.   friend bool operator!=(BigInteger const &a, BigInteger const &b);
  29.   friend bool operator!=(BigInteger const &a, int const b);
  30.   friend BigInteger operator+(BigInteger const a, BigInteger const b);
  31.  
  32.   friend std::ostream &operator<<(std::ostream &stream, BigInteger c);
  33.   void dump() {
  34.     std::cout << "n = " << this->n << ": ";
  35.     for (int i = 0; i < this->n; i++)
  36.       std::cout << i << ":" << this->b[i] << ",";
  37.     std::cout << std::endl;
  38.   }
  39. };
  40.  
  41. BigInteger::BigInteger() : n(0), b(0) {};
  42. BigInteger::BigInteger(const BigInteger &ob) {
  43.   this->n = ob.n;
  44.   if (ob.n == 0) {
  45.     this->b = 0;
  46.   } else {
  47.     this->b = new int[ob.n];
  48.     for (int i = 0; i < ob.n; i++)
  49.       this->b[i] = ob.b[i];
  50.   }
  51. }
  52.  
  53. BigInteger::BigInteger(const int n) {
  54.   assert(n < CMASK);
  55.   this->n = 1;
  56.   this->b = new int[1]; /* need */
  57.   this->b[0] = n;
  58. }
  59.  
  60. BigInteger BigInteger::operator=(BigInteger ob) {
  61.   this->n = ob.n;
  62.   if (ob.n == 0) {
  63.     delete this->b;
  64.     this->b = 0;
  65.   } else {
  66.     delete [] this->b;
  67.     this->b = new int[ob.n];
  68.     for (int i = 0; i < ob.n; i++) {
  69.       this->b[i] = ob.b[i];
  70.     }
  71.   }
  72.   return *this;
  73. }
  74.  
  75. BigInteger BigInteger::operator=(int n) {
  76.   assert(n < CMASK);
  77.   if (this->n > 0) {
  78.     this->b[0] = n;
  79.     for (int i = 1; i < n; i++)
  80.       this->b[i] = 0;
  81.   } else {
  82.     this->b = new int[1];
  83.     this->b[0] = n;
  84.     this->n = 1;
  85.   }
  86.   return *this;
  87. }
  88.  
  89. BigInteger::~BigInteger() {  delete [] this->b; }
  90.  
  91. bool operator==(BigInteger const &a, BigInteger const &b) {
  92.   int i;
  93.   bool isEqual = true;
  94.   for (i = 0; i < a.n; i++)
  95.     if (i < b.n && a.b[i] != b.b[i]) {
  96.       isEqual = false;
  97.       break;
  98.     }
  99.   if (i < a.n) {
  100.     for (; i < a.n; i++)
  101.       if (a.b[i] != 0) {
  102.         isEqual = false;
  103.         break;
  104.       }
  105.   } else if (i < b.n) {
  106.     for (;i < b.n; i++)
  107.       if (b.b[i] != 0) {
  108.         isEqual = false;
  109.         break;
  110.       }
  111.   }
  112.   return isEqual;
  113. }
  114.  
  115. bool operator==(BigInteger const &a, int const b) {
  116.   assert(b < CMASK);
  117.   bool isEqual = true;
  118.   if (a.b[0] != b)
  119.     isEqual = false;
  120.   for (int i = 1; i < a.n; i++)
  121.     if (a.b[i] != 0)
  122.       isEqual = false;
  123.   return isEqual;
  124. }
  125.  
  126. bool operator!=(BigInteger const &a, BigInteger const &b) { return !(a == b); }
  127. bool operator!=(BigInteger const &a, int const b) { return !(a == b); }
  128.  
  129. BigInteger operator+(BigInteger const a, BigInteger const b) {
  130.   BigInteger r;
  131.   BigInteger const * more_ab;
  132.   int less_n;
  133.   if (a.n > b.n) {
  134.     r.n = a.n;
  135.     more_ab = &a;
  136.     less_n = b.n;
  137.   } else {
  138.     r.n = b.n;
  139.     more_ab = &b;
  140.     less_n = a.n;
  141.   }
  142.   r.b = new int [r.n];
  143.   int i, carry = 0;
  144.   for (i = 0; i < less_n; i++) {
  145.     int s = a.b[i] + b.b[i] + carry;
  146.     if (s >= CMASK) {
  147.       carry = 1;
  148.       r.b[i] = (s  & BMASK);
  149.     } else {
  150.       carry = 0;
  151.       r.b[i] = s; /* need */
  152.     }
  153.   }
  154.   for (;i < r.n; i++) {
  155.     int s = more_ab->b[i] + carry;
  156.     if (s >= CMASK) {
  157.       carry = 1;
  158.       r.b[i] = (s  & BMASK); /* need */
  159.     } else {
  160.       carry = 0;
  161.       r.b[i] = (s  & BMASK); /* need */ /* not to insert break keyword.*/
  162.     }
  163.   }
  164.   if (carry) {
  165.     int *new_body = new int [r.n + 1];
  166.     for (i = 0; i < r.n; i++)
  167.       new_body[i] = r.b[i];
  168.     new_body[i] = carry;
  169.     delete [] r.b;
  170.     r.b = new_body;
  171.     r.b[r.n] = 1; /* need */
  172.     r.n++;
  173.   }
  174.   return r;
  175. }
  176.  
  177. bool BigInteger::iszero(BigInteger &n) {
  178.   bool isZero = true;
  179.   for (int i = 0; i < n.n; i++)
  180.     if (n.b[i] != 0) {
  181.       isZero = false;
  182.       break;
  183.     }
  184.   return isZero;
  185. }
  186.  
  187. std::ostream &operator<<(std::ostream &stream, BigInteger c) {
  188.   std::basic_string<char> mod10;
  189.   BigInteger q, n;
  190.   int mod;
  191.  
  192.   n = c;
  193.   for(;;) {
  194.     /* div10(n, q, mod); */
  195.     {
  196.       q = n;
  197.       mod = 0;
  198.       for (int i = 0; i < n.n * BIT; i++) {
  199.         /* shift_div(mod, q); */
  200.         {
  201.           int cy, i;
  202.  
  203.           cy = 0;
  204.           for (i = 0; i < n.n; i++) {
  205.             q.b[i] = q.b[i] << 1;
  206.             if (cy)
  207.               q.b[i] = q.b[i] | 0x01;
  208.             cy = (q.b[i] >> BIT);
  209.             q.b[i] = q.b[i] & BMASK;
  210.           }
  211.           mod = mod << 1;
  212.           if (cy)
  213.             mod = mod | 0x01;
  214.  
  215.         }
  216.         if (mod >= 10) {
  217.           q.b[0] = q.b[0] | 0x01;
  218.           mod = mod - 10;
  219.         }
  220.       }
  221.     }
  222.     if (BigInteger::iszero(q) && mod == 0)
  223.       break;
  224.     mod10 = (char)('0' + mod) + mod10;
  225.     n = q;
  226.   }
  227.   return stream << mod10;
  228. }
  229.  
  230. int memoOK = 0;
  231. int calcSAD = 0;
  232.  
  233. //-----------------------------------------
  234. BigInteger combination(std::map<std::pair<int, int>, BigInteger*> &bmap, int m, int n) {
  235.   BigInteger *r;
  236.   if (m == 1 && n == 1)
  237.     return BigInteger(1);
  238.   if (n == m || n == 0)
  239.     return BigInteger(1);
  240.   std::map<std::pair<int, int>, BigInteger*>::iterator p;
  241.   p = bmap.find(std::pair<int, int>(m, n));
  242.   if (p != bmap.end()) {
  243.     memoOK++;
  244.     return *(p->second);
  245.   }
  246.   calcSAD++;
  247.   r = new BigInteger(combination(/*ref*/bmap, m - 1, n) + combination(/*ref*/bmap, m - 1, n - 1));
  248.   bmap.insert(std::pair<std::pair<int, int>, BigInteger*>{{m, n}, r});
  249.   return *r;
  250. }
  251.  
  252. #if 1
  253. int main() {
  254.   std::map<std::pair<int, int>, BigInteger*> map;
  255. //  int n, m;
  256. //  m = 10; n = m / 10; std::cout << m << "C" << n << " = " << combination(map, m, n) << std::endl;
  257. //  m = 50; n = m / 10; std::cout << m << "C" << n << " = " << combination(map, m, n) << std::endl;
  258. //  m = 100; n = m / 10; std::cout << m << "C" << n << " = " << combination(map, m, n) << std::endl;
  259. //  m = 500; n = m / 10; std::cout << m << "C" << n << " = " << combination(map, m, n) << std::endl;
  260. //  m = 1000; n = m / 10; std::cout << m << "C" << n << " = " << combination(map, m, n) << std::endl;
  261. //  m = 5000; n = m / 10; std::cout << m << "C" << n << " = " << combination(map, m, n) << std::endl;
  262.   std::cout << "12345_C_1234 = " << combination(map, 12345, 1234) << std::endl;
  263.   std::cout << "memoOK = " << memoOK << ", calcSAD = " << calcSAD << std::endl;
  264.   return 0;
  265. }
  266. #if 0
  267. result:
  268. 12345_C_1234 =
  269. 3086885767069095503480695111424066468076768108203466995814541390718951103801570583489928494101503050
  270. 0292077297554684804960737924867216828315691317303413860493913341300084570314857521290316851004139592
  271. 7083138896681470143354608658171166250358749153713956096771732322085032482479487878933881076915545066
  272. 2864835867726094240512538472562072683473279411726874259740937085368798537861531861971004413640504802
  273. 7694748183923096850593142581605629287003228790407134261770854027866312797870067857940190882137657394
  274. 8265045299510198493744452604897343180259149485574383580858918580385167344846291821022600851930044614
  275. 4785638481712311789538314335414568759529054060259054198879183163748013499495992368974335667878279296
  276. 1767289577615713022309748134199206025888996985649500334563692731136734157551589580190056154497515274
  277. 8226685202788487799030447453467949519652858288213868033305846249000299679752350579692429988444670871
  278. 0159684542628532037799668969751273251776710129478802076798707594328478890065556036853631772623521476
  279. 9448117868302318029248108264381830842610610899255656915305311760106411559221114009794147119652629290
  280. 0146537681400090396229992625760014310609367708918732468995893898417943345472971473085883190172466476
  281. 7700403107772601840335022956257502937776942070712111259879452426262946735867739225133683261860098395
  282. 4993981678669499906942575426171432655879698563584738702214885828547089328855866325437787011135269645
  283. 1452874629615675887803365473909384314883727195457911779889643707929790557130821739575849980622351601
  284. 5358368895318957760171166340726732456498271501435471797611983683387606092104170533539035321564321045
  285. 4089478065309146924902443178857863508110989160457029232861433029042255144361096970770355858337901172
  286. 12044535391439524029513049239849989152000
  287. memoOK = 13698630, calcSAD = 13710974
  288. #endif
  289. //-----------------------------------------
  290. #endif
  291.  
  292. #if 0
  293. int c(int m, int n) {
  294.   int p = 1;
  295.   for (int i = 0, denom = m, num = 1; i < n; i++)
  296.     p = p * denom-- / num++;
  297.   if (m == 8 && n == 3)
  298.     return 0;
  299.   return p;
  300. }
  301.  
  302. #define N 20
  303. int main() {
  304.   std::map<std::pair<int, int>, BigInteger> map;
  305.   for (int i = 1; i < N; i++) {
  306.     for (int j = 0; j <= i; j++) {
  307.       std::cout << combination(/*ref*/map, i, j);
  308.       std::cout << ":";
  309.       std::cout << c(i, j);
  310.       std::cout << ", ";
  311.     }
  312.     std::cout << std::endl;
  313.   }
  314.   return 0;
  315. }
  316. #endif
  317. /* end */
  318.  
Time limit exceeded #stdin #stdout 5s 403392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/H8lKio
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!