Skip to main content
制約に合わせて色々ある解法へのヒントとしてリンクを追加しました
ソース リンク
nekketsuuu
  • 2.4万
  • 12
  • 53
  • 117

オーバーフローが起こっているのはこの計算をするときです。

(n - r + 1) * combi(n, r - 1) / r

たとえば combi(64, 32) の呼び出しでは以下の計算をすることになりますが、

33 * combi(64, 31) / 32

₆₄C₃₁ = 1,777,090,076,065,542,336 なので、これに 33 を掛けると 2⁶⁴ - 1 = 9,223,372,036,854,775,807 を超えます。

したがって、このオーバーフローが起こらないように計算式を修正する必要があります。剰余がある元で二項係数を求める方法は色々あります色々ありますが、今回の場合はパスカルの三角形で求めるのが簡単そうです。つまり、

nCr = (n-1)Cr + (n-1)C(r-1)

という式を元に順番に足し合わせることで求めることができます。これなら途中式が足し算だけなので計算途中に剰余をとることができます。

オーバーフローが起こっているのはこの計算をするときです。

(n - r + 1) * combi(n, r - 1) / r

たとえば combi(64, 32) の呼び出しでは以下の計算をすることになりますが、

33 * combi(64, 31) / 32

₆₄C₃₁ = 1,777,090,076,065,542,336 なので、これに 33 を掛けると 2⁶⁴ - 1 = 9,223,372,036,854,775,807 を超えます。

したがって、このオーバーフローが起こらないように計算式を修正する必要があります。剰余がある元で二項係数を求める方法は色々ありますが、今回の場合はパスカルの三角形で求めるのが簡単そうです。つまり、

nCr = (n-1)Cr + (n-1)C(r-1)

という式を元に順番に足し合わせることで求めることができます。これなら途中式が足し算だけなので計算途中に剰余をとることができます。

オーバーフローが起こっているのはこの計算をするときです。

(n - r + 1) * combi(n, r - 1) / r

たとえば combi(64, 32) の呼び出しでは以下の計算をすることになりますが、

33 * combi(64, 31) / 32

₆₄C₃₁ = 1,777,090,076,065,542,336 なので、これに 33 を掛けると 2⁶⁴ - 1 = 9,223,372,036,854,775,807 を超えます。

したがって、このオーバーフローが起こらないように計算式を修正する必要があります。剰余がある元で二項係数を求める方法は色々ありますが、今回の場合はパスカルの三角形で求めるのが簡単そうです。つまり、

nCr = (n-1)Cr + (n-1)C(r-1)

という式を元に順番に足し合わせることで求めることができます。これなら途中式が足し算だけなので計算途中に剰余をとることができます。

typo
ソース リンク
nekketsuuu
  • 2.4万
  • 12
  • 53
  • 117

オーバーフローが起こっているのはこの計算をするときです。

(n - r + 1) * combi(n, r - 1) / r

たとえば combi(64, 32) の呼び出しでは以下の計算をすることになりますが、

33 * combi(64, 31) / 32

₆₄C₃₁ = 1,777,090,076,065,542,336 なので、これに 33 を掛けると 2⁶⁴ - 1 = 9,223,372,036,854,775,807 を超えます。

したがって、このオーバーフローが起こらないように計算式を修正する必要があります。剰余がある元で二項係数を求める方法は色々ありますが、今回の場合はパスカルの三角形で求めるのが簡単そうです。つまり、

nCr = (n-1)Cr + (n-1)C(r-1)

という式を元に順番に足し合わせることで求めることができます。これなら途中式が足し算だけなので計算途中に剰余をとることができます。

オーバーフローが起こっているのはこの計算をするときです。

(n - r + 1) * combi(n, r - 1) / r

たとえば combi(64, 32) の呼び出しでは以下の計算をすることになりますが、

33 * combi(64, 31) / 32

₆₄C₃₁ = 1,777,090,076,065,542,336 なので、これに 33 を掛けると 2⁶⁴ = 9,223,372,036,854,775,807 を超えます。

したがって、このオーバーフローが起こらないように計算式を修正する必要があります。剰余がある元で二項係数を求める方法は色々ありますが、今回の場合はパスカルの三角形で求めるのが簡単そうです。つまり、

nCr = (n-1)Cr + (n-1)C(r-1)

という式を元に順番に足し合わせることで求めることができます。これなら途中式が足し算だけなので計算途中に剰余をとることができます。

オーバーフローが起こっているのはこの計算をするときです。

(n - r + 1) * combi(n, r - 1) / r

たとえば combi(64, 32) の呼び出しでは以下の計算をすることになりますが、

33 * combi(64, 31) / 32

₆₄C₃₁ = 1,777,090,076,065,542,336 なので、これに 33 を掛けると 2⁶⁴ - 1 = 9,223,372,036,854,775,807 を超えます。

したがって、このオーバーフローが起こらないように計算式を修正する必要があります。剰余がある元で二項係数を求める方法は色々ありますが、今回の場合はパスカルの三角形で求めるのが簡単そうです。つまり、

nCr = (n-1)Cr + (n-1)C(r-1)

という式を元に順番に足し合わせることで求めることができます。これなら途中式が足し算だけなので計算途中に剰余をとることができます。

ソース リンク
nekketsuuu
  • 2.4万
  • 12
  • 53
  • 117

オーバーフローが起こっているのはこの計算をするときです。

(n - r + 1) * combi(n, r - 1) / r

たとえば combi(64, 32) の呼び出しでは以下の計算をすることになりますが、

33 * combi(64, 31) / 32

₆₄C₃₁ = 1,777,090,076,065,542,336 なので、これに 33 を掛けると 2⁶⁴ = 9,223,372,036,854,775,807 を超えます。

したがって、このオーバーフローが起こらないように計算式を修正する必要があります。剰余がある元で二項係数を求める方法は色々ありますが、今回の場合はパスカルの三角形で求めるのが簡単そうです。つまり、

nCr = (n-1)Cr + (n-1)C(r-1)

という式を元に順番に足し合わせることで求めることができます。これなら途中式が足し算だけなので計算途中に剰余をとることができます。