OJ Board

I was wondering whether there is a smart way of calculating n choose m without having the possibility of an overflow during the calculation (when it's given that the result is within bounds).

I always use this method

[java]static long choose(int n, int m) {
if(m > n/2) return choose(n, n-m);
long t = 1;
for(int i=1; i<=m; i++)
t = (t * (n-m+i))/i;
return t;
}[/java]

but this could overflow because I multiply before I divide. Is there a way to avoid an overflow without factorizing n and m?

This works. The computation takes n^2 time, but you only have to do it once, and I doubt you need to store that many.

[cpp]
#include <iostream>
using namespace std;
static long choose(int n, int m) {
if(m > n/2) return choose(n, n-m);
long t = 1;
for(int i=1; i<=m; i++)
t = (t * (n-m+i))/i;
return t;
}

int choose_tbl[100][100];

long choose2(int n, int m) {
int &ret = choose_tbl[n][m];
if (ret != -1) return ret;
ret = choose2(n-1, m) + choose2(n-1, m-1);
return ret;
}

int main() {
for (int i = 0; i < 100; ++i)
for (int j = 0; j < 100; ++j)
if (j < i) choose_tbl[j] = -1;
else choose_tbl[j] = 1;


for (int i = 0; i < 100; ++i) choose_tbl[0] = choose_tbl = 1;
for (int i = 0; i < 12; ++i) {
for (int j = 0; j < 12; ++j)
if (choose2(i, j) != choose(i, j))
cout << i << "\t" << j << "\t" << choose(i, j) << "\t" << choose2(i, j) << "\n";
//cout << i << "\t" << j << "\t" << choose2(i, j) << "\n";
}
}
[/cpp]

a little hint : prime factorization

titid_gede wrote:a little hint : prime factorization

a little hint... next time read the whole post you are replying to

Maniac wrote:but this could overflow because I multiply before I divide. Is there a way to avoid an overflow without factorizing n and m?

You can use GCD. When computing (A*B)/C, let G=GCD(A,C) then

(A*B)/C = (A/G) * (B/(C/G)).

Yes, your right. That would certainly avoid the overflow. Thanks!