IPO 見本

競プロ典型 90 問 42 日目 - Multiple of 9（★4）

import Control.Monad
import qualified Data.Vector.Unboxed.Mutable as UM

main = readLn >>= sol >>= print

sol k = case k `mod` 9 of
  0 -> f9 k
  _ -> return 0

p = 10^9+7

f9 k = do
  u <- UM.replicate (k+9) 0
  forM_ [0..7] $ \i -> UM.write u i (0 :: Int)
  UM.write u 8 1
  forM_ [9..k+8] $ \i ->
    foldM (\s j -> (`mod` p) . (+ s) <$> UM.read u j) 0 [i-9..i-1] 
      >>= UM.write u i
  UM.read u (k+8)