質問: 0){ return 1; } return n*factn(n - 1); } int nkchoose(int n, int k){ return factn(n)/(factn(k)*factn(n-k)); } int main(void){ int n, k; scanf("%d %d", &n, &k); printf("%d\n", nkchoose(n,k)); return 0; }
回答: オーバーフローしているものと思われます。 階乗計算は数の増加が早く、12! = 479001600の時点で符号付32ビット整数が表せる整数の範囲を超え、 21! = 51090942171709440000で符号付64ビット整数の範囲を超えます。 二項係数は要はnCrなので、乗算が少なくなるように工夫すればいいのです。 階乗を使わず、 n(n-1)(n-2)...(n-r+1)/r(r-1)(r-2)...1 として計算します。 rがnの半分より大きい場合は、nCr = nCn-rを使えば乗算回数を減らせます。