#include <iostream>
#include <string>
#include <map>
#include <cctype>
#include <cassert>
enum {
BIT = 30,
CMASK = 1 << BIT,
BMASK = CMASK - 1
};
class BigInteger {
private:
int n;
int *b;
private:
static bool iszero(BigInteger &n);
public:
BigInteger();
BigInteger(const BigInteger &ob);
BigInteger(const int n);
~BigInteger();
BigInteger operator=(BigInteger n);
BigInteger operator=(int n);
friend bool operator==(BigInteger const &a, BigInteger const &b);
friend bool operator==(BigInteger const &a, int const b);
friend bool operator!=(BigInteger const &a, BigInteger const &b);
friend bool operator!=(BigInteger const &a, int const b);
friend BigInteger operator+(BigInteger const a, BigInteger const b);
friend std::ostream &operator<<(std::ostream &stream, BigInteger c);
void dump() {
std::cout << "n = " << this->n << ": ";
for (int i = 0; i < this->n; i++)
std::cout << i << ":" << this->b[i] << ",";
std::cout << std::endl;
}
};
BigInteger::BigInteger() : n(0), b(0) {}
BigInteger::BigInteger(const BigInteger &ob) {
this->n = ob.n;
if (ob.n == 0) {
this->b = 0;
} else {
this->b = new int[ob.n];
for (int i = 0; i < ob.n; i++)
this->b[i] = ob.b[i];
}
}
BigInteger::BigInteger(const int n) {
assert(n < CMASK);
this->n = 1;
this->b = new int[1]; /* need */
this->b[0] = n;
}
BigInteger BigInteger::operator=(BigInteger ob) {
this->n = ob.n;
if (ob.n == 0) {
delete this->b;
this->b = 0;
} else {
delete [] this->b;
this->b = new int[ob.n];
for (int i = 0; i < ob.n; i++) {
this->b[i] = ob.b[i];
}
}
return *this;
}
BigInteger BigInteger::operator=(int n) {
assert(n < CMASK);
if (this->n > 0) {
this->b[0] = n;
for (int i = 1; i < n; i++)
this->b[i] = 0;
} else {
this->b = new int[1];
this->b[0] = n;
this->n = 1;
}
return *this;
}
BigInteger::~BigInteger() { delete [] this->b; }
bool operator==(BigInteger const &a, BigInteger const &b) {
int i;
bool isEqual = true;
for (i = 0; i < a.n; i++)
if (i < b.n && a.b[i] != b.b[i]) {
isEqual = false;
break;
}
if (i < a.n) {
for (; i < a.n; i++)
if (a.b[i] != 0) {
isEqual = false;
break;
}
} else if (i < b.n) {
for (;i < b.n; i++)
if (b.b[i] != 0) {
isEqual = false;
break;
}
}
return isEqual;
}
bool operator==(BigInteger const &a, int const b) {
assert(b < CMASK);
bool isEqual = true;
if (a.b[0] != b)
isEqual = false;
for (int i = 1; i < a.n; i++)
if (a.b[i] != 0)
isEqual = false;
return isEqual;
}
bool operator!=(BigInteger const &a, BigInteger const &b) { return !(a == b); }
bool operator!=(BigInteger const &a, int const b) { return !(a == b); }
BigInteger operator+(BigInteger const a, BigInteger const b) {
BigInteger r;
BigInteger const * more_ab;
int less_n;
if (a.n > b.n) {
r.n = a.n;
more_ab = &a;
less_n = b.n;
} else {
r.n = b.n;
more_ab = &b;
less_n = a.n;
}
r.b = new int [r.n];
int i, carry = 0;
for (i = 0; i < less_n; i++) {
int s = a.b[i] + b.b[i] + carry;
if (s >= CMASK) {
carry = 1;
r.b[i] = (s & BMASK);
} else {
carry = 0;
r.b[i] = s; /* need */
}
}
for (;i < r.n; i++) {
int s = more_ab->b[i] + carry;
if (s >= CMASK) {
carry = 1;
r.b[i] = (s & BMASK); /* need */
} else {
carry = 0;
r.b[i] = (s & BMASK); /* need */ /* not to insert break keyword.*/
}
}
if (carry) {
int *new_body = new int [r.n + 1];
for (i = 0; i < r.n; i++)
new_body[i] = r.b[i];
new_body[i] = carry;
delete [] r.b;
r.b = new_body;
r.b[r.n] = 1; /* need */
r.n++;
}
return r;
}
bool BigInteger::iszero(BigInteger &n) {
bool isZero = true;
for (int i = 0; i < n.n; i++)
if (n.b[i] != 0) {
isZero = false;
break;
}
return isZero;
}
std::ostream &operator<<(std::ostream &stream, BigInteger c) {
std::basic_string<char> mod10;
BigInteger q, n;
int mod;
n = c;
for(;;) {
/* div10(n, q, mod); */
{
q = n;
mod = 0;
for (int i = 0; i < n.n * BIT; i++) {
/* shift_div(mod, q); */
{
int cy, i;
cy = 0;
for (i = 0; i < n.n; i++) {
q.b[i] = q.b[i] << 1;
if (cy)
q.b[i] = q.b[i] | 0x01;
cy = (q.b[i] >> BIT);
q.b[i] = q.b[i] & BMASK;
}
mod = mod << 1;
if (cy)
mod = mod | 0x01;
}
if (mod >= 10) {
q.b[0] = q.b[0] | 0x01;
mod = mod - 10;
}
}
}
if (BigInteger::iszero(q) && mod == 0)
break;
mod10 = (char)('0' + mod) + mod10;
n = q;
}
return stream << mod10;
}
int memoOK = 0;
int calcSAD = 0;
//-----------------------------------------
BigInteger combination(std::map<std::pair<int, int>, BigInteger*> &bmap, int m, int n) {
BigInteger *r;
if (m == 1 && n == 1)
return BigInteger(1);
if (n == m || n == 0)
return BigInteger(1);
std::map<std::pair<int, int>, BigInteger*>::iterator p;
p = bmap.find(std::pair<int, int>(m, n));
if (p != bmap.end()) {
memoOK++;
return *(p->second);
}
calcSAD++;
r = new BigInteger(combination(/*ref*/bmap, m - 1, n) + combination(/*ref*/bmap, m - 1, n - 1));
std::pair<int, int> k = std::pair<int, int>(m, n);
bmap.insert(std::pair<std::pair<int, int>, BigInteger*>(k, r));
return *r;
}
#if 1
int main() {
std::map<std::pair<int, int>, BigInteger*> map;
int n, m;
// m = 10; n = m / 10; std::cout << m << "C" << n << " = " << combination(map, m, n) << std::endl;
// m = 50; n = m / 10; std::cout << m << "C" << n << " = " << combination(map, m, n) << std::endl;
m = 100; n = m / 10; std::cout << m << "C" << n << " = " << combination(map, m, n) << std::endl;
// m = 500; n = m / 10; std::cout << m << "C" << n << " = " << combination(map, m, n) << std::endl;
// m = 1000; n = m / 10; std::cout << m << "C" << n << " = " << combination(map, m, n) << std::endl;
// m = 5000; n = m / 10; std::cout << m << "C" << n << " = " << combination(map, m, n) << std::endl;
std::cout << "12345_C_1234 = " << combination(map, 12345, 1234) << std::endl;
std::cout << "memoOK = " << memoOK << ", calcSAD = " << calcSAD << std::endl;
std::map<std::pair<int, int>, BigInteger*>::iterator p;
for (p = map.begin(); p != map.end(); p++) {
delete p->second;
}
return 0;
}
#if 0
result:
12345_C_1234 =
3086885767069095503480695111424066468076768108203466995814541390718951103801570583489928494101503050
0292077297554684804960737924867216828315691317303413860493913341300084570314857521290316851004139592
7083138896681470143354608658171166250358749153713956096771732322085032482479487878933881076915545066
2864835867726094240512538472562072683473279411726874259740937085368798537861531861971004413640504802
7694748183923096850593142581605629287003228790407134261770854027866312797870067857940190882137657394
8265045299510198493744452604897343180259149485574383580858918580385167344846291821022600851930044614
4785638481712311789538314335414568759529054060259054198879183163748013499495992368974335667878279296
1767289577615713022309748134199206025888996985649500334563692731136734157551589580190056154497515274
8226685202788487799030447453467949519652858288213868033305846249000299679752350579692429988444670871
0159684542628532037799668969751273251776710129478802076798707594328478890065556036853631772623521476
9448117868302318029248108264381830842610610899255656915305311760106411559221114009794147119652629290
0146537681400090396229992625760014310609367708918732468995893898417943345472971473085883190172466476
7700403107772601840335022956257502937776942070712111259879452426262946735867739225133683261860098395
4993981678669499906942575426171432655879698563584738702214885828547089328855866325437787011135269645
1452874629615675887803365473909384314883727195457911779889643707929790557130821739575849980622351601
5358368895318957760171166340726732456498271501435471797611983683387606092104170533539035321564321045
4089478065309146924902443178857863508110989160457029232861433029042255144361096970770355858337901172
12044535391439524029513049239849989152000
memoOK = 13698630, calcSAD = 13710974
#endif
//-----------------------------------------
#endif
#if 0
int c(int m, int n) {
int p = 1;
for (int i = 0, denom = m, num = 1; i < n; i++)
p = p * denom-- / num++;
if (m == 8 && n == 3)
return 0;
return p;
}
#define N 20
int main() {
std::map<std::pair<int, int>, BigInteger> map;
for (int i = 1; i < N; i++) {
for (int j = 0; j <= i; j++) {
std::cout << combination(/*ref*/map, i, j);
std::cout << ":";
std::cout << c(i, j);
std::cout << ", ";
}
std::cout << std::endl;
}
return 0;
}
#endif
/* end */