回答編集履歴
1
nCr
test
CHANGED
@@ -3,3 +3,15 @@
|
|
3
3
|
階乗計算は数の増加が早く、12! = 479001600の時点で符号付32ビット整数が表せる整数の範囲を超え、
|
4
4
|
|
5
5
|
21! = 51090942171709440000で符号付64ビット整数の範囲を超えます。
|
6
|
+
|
7
|
+
|
8
|
+
|
9
|
+
二項係数は要はnCrなので、乗算が少なくなるように工夫すればいいのです。
|
10
|
+
|
11
|
+
階乗を使わず、
|
12
|
+
|
13
|
+
n(n-1)(n-2)...(n-r+1)/r(r-1)(r-2)...1
|
14
|
+
|
15
|
+
として計算します。
|
16
|
+
|
17
|
+
rがnの半分より大きい場合は、nCr = nCn-rを使えば乗算回数を減らせます。
|