HaskellでAtCoder ABC145-Dにおいて、自分で以下の書いたコードのどこで0除算がされているかわからない。

Question

タイトル通りですが、下記のコードにおいてどこで0除算がされているかわかりません。

該当のAtCoderリンク

当方Haskellを始めたばかりで、このプログラムが問題をとけるプログラムなのかどうかという確証も持てませんが、下記の二点について助言をいただきたいです。

1. 0除算が発生している箇所
2. このプログラムがこの問題を解決できるものか
3. 1において、解決できない場合、正しいアルゴリズムはなにか。また、どうやって実装するか。（流れだけ）

試したこと

• m<=0のときの返り値を1で一定にする
• n==mのときの返り値を1で一定にする

該当コード

import           Control.Monad
import           Data.Array
import qualified Data.ByteString.Char8 as BS
import           Data.List
import           Data.Maybe

readInts :: IO [Int]
readInts = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

main = do
  [x, y] <- map read . words <$> getLine
  print $ solve x y `mod` 1000000007

solve :: Int -> Int -> Int
solve x y = sum [check x y a | a <- [0 .. x]]

check :: Int -> Int -> Int -> Int
check x y a
  | x - a `mod` 2 == 1 = 0
  | y == (2 * a) + b = c (a + b) a
  | otherwise = 0
  where
    b = (x - a) `div` 2
    c n m = product [n,n - 1 .. 1] `div` (product [m,m - 1 .. 1] * product [n - m,n - m - 1 .. 1])

エラーが起きるテスト（入力）

999999 999999

正しい出力

151840682

手元環境でのエラー（Intellij-Haskell）

/usr/bin/stack build --exec AtCoder-exe
999999 999999
AtCoder-exe: divide by zero
Received ExitFailure 1 when running
Raw command://ここには実行ファイルの絶対パスがあります。

Answer 1

1から66までの素因数には2が64個以上含まれているので、product [1..n]はnが66以上だと結果が0になってしまいます(その前にオーバーフローしますが…)。cの定義を工夫し、オーバーフローしないような実装にしましょう(参考: https://stackoverflow.com/questions/1838368/calculating-the-amount-of-combinations )

Comments

[RheoTommy]

なるほど…。ちなみに、この方法以外に、組み合わせのnCrを求める方法ありますかね？
便利な関数とかがあればいいのですが…。

このコードは
nCr=n!/r!(n-r)!
をもとに作ったのですが、確かに計算結果は大きくなりますね…。

[RheoTommy]

確か重複のない組み合わせをリストで返す関数があった気がします。

それを使い、lenghtで長さを求めればいいですかね？

ただ、実行時間が測りしれなさそうです。

Answer 2

https://blog.miz-ar.info/2018/01/debugging-haskell-program/ を参考にスタックトレースを出したりtraceShowIdしたりしてわかったことを報告しますと、
c関数における div の分母

(product [m,m - 1 .. 1] * product [n - m,n - m - 1 .. 1])

が0を返したことによるエラーのようです。
詳細は私もわからないのですが、 m がある程度大きな数の場合 product [m,m - 1 .. 1] が 0 を返してしまうようです。

例:

> product [100, 99 .. 1] :: Int
0

桁あふれが起きているのだと思いますが、なぜ 0 になるかはわからず済みません。

これが正しい回答になるかはわかりませんが、とりあえず対症療法をするなら Int の代わりに Integer を使えば良いでしょう。
ただし、当然実行時間はその分長くなるので、TLEになる可能性が高いですが...。