Submission #43753179

---

Source Code Expand

#!/usr/bin/env stack
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeApplications #-}

#ifdef DEBUG
import Debug.Trace (traceShow)
#endif

import Control.Monad (forM_, when)
import Data.Array.IO (
  IOArray,
  Ix,
  MArray (newArray),
  readArray,
  writeArray,
 )
import qualified Data.ByteString.Char8 as BS
import Data.Char (isSpace)
import Data.List (unfoldr)
import Debug.Trace (traceShow)

solve :: Int -> IO IntMod
solve k
  | k `mod` 9 == 0 = do
    -- 桁和が K になる、0 を含まない整数の通り数
    dp <- newArray @IOArray (0, k) 0

    writeArray dp 0 1

    forM_ [0 .. k - 1] $ \i -> do
      x <- readArray dp i

      forM_ [1 .. 9] $ \j -> do
        when (i + j <= k) $ do
          updateWith (+) dp (i + j) x

    readArray dp k
  | otherwise = return 0

main :: IO ()
main = do
  k <- readLn @Int

  (IntMod x) <- solve k

  print x

{-- Library --}

modulus :: Int
modulus = 1000000007 -- 10^9 + 7

newtype IntMod = IntMod Int deriving (Eq, Show)

instance Num IntMod where
  IntMod x + IntMod y = IntMod ((x + y) `mod` modulus)
  IntMod x - IntMod y = IntMod ((x - y) `mod` modulus)
  IntMod x * IntMod y = IntMod ((x * y) `mod` modulus)
  fromInteger n = IntMod (fromInteger (n `mod` fromIntegral modulus))
  abs = abs
  signum = signum

updateWith :: (MArray a e m, Ix i) => (e -> e -> e) -> a i e -> i -> e -> m ()
updateWith f arr ix x = do
  v <- readArray arr ix
  writeArray arr ix $! f v x
{-# INLINE updateWith #-}

getInts :: IO [Int]
getInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

getTuple :: IO (Int, Int)
getTuple = do
  [a, b] <- getInts
  return (a, b)

#ifdef DEBUG
dbg :: Show a => a -> ()
dbg !x = let !_ = traceShow x () in ()
#else
dbg :: Show a => a -> ()
dbg _ = ()
#endif

Submission Info

Compile Error

Loaded package environment from /home/contestant/.ghc/x86_64-linux-8.8.3/environments/default

Judge Result