Submission #46395920

---

Source Code Expand

import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

import Data.Array.ST
import Data.Array
import Control.Monad

main = do
  [n,x] <- bsGetLnInts
  ts <- bsGetLnInts
  let ans = abc323e n x ts
  print ans

bsGetLnInts :: IO [Int]
bsGetLnInts = BS.getLine >>= return . unfoldr (BS.readInt . BS.dropWhile isSpace)

abc323e :: Int -> Int -> [Int] -> Int
abc323e n x ts@(t1:_) = ans
  where
-- 1/n のmodP
    recipN = modRecip n
-- 時刻0～Xが、新たな曲を選択して始めるタイミングになっている確率
-- 時刻0は1、それ以降はTi後に1/nずつ配るDP
--    pa = distributingDPga (0,x) [(0,1)] df (reg . sum)
    pa = distributingDP (0,x) 0 [(0,1)] df add
    df t p = [(t1, q) | t1 <- takeWhile (x >=) $ map (t +) sts] where q = mul p recipN
    sts = sort ts
-- 時刻 X-T1+1～X の確率に、T1が選択される確率1/Nを掛けた総和が答え
    ans = mul recipN $ reg $ sum $ drop (x - t1 + 1) $ elems pa

-- mod
modBase = 998244353
reg x = mod x modBase
add x y = reg $ x + y
mul x y = reg $ x * y

-- @gotoki_no_joe
modRecip a = powerish mul 1 a (modBase - 2)
powerish mul i a b = foldl' {-'-} mul i [p | (True, p) <- zip bs ps]
  where
    bs = map odd $ takeWhile (0 <) $ iterate (flip div 2) b
    ps = iterate (\x -> mul x x) a

-- 配るDPをmuable arrayで元々の仕組み通りに実装
distributingDP :: Ix i => (i,i) -> x -> [(i,x)] -> (i -> x -> [(i,x)]) -> (x -> x -> x) -> Array i x
distributingDP bnds i inis df op = runSTArray $
  do
    arr <- newArray bnds i
    forM_ inis $ uncurry (writeArray arr)
    forM_ (range bnds) $ \i -> do
      x <- readArray arr i
      forM_ (df i x) $ \(j, y) -> do
        z <- readArray arr j
        writeArray arr j $! op y z
    return arr

Submission Info

Compile Error

app/Main.hs:9:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: main :: IO ()
  |
9 | main = do
  | ^^^^

app/Main.hs:19:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘abc323e’:
        Patterns of type ‘Int’, ‘Int’, ‘[Int]’ not matched: _ _ []
   |
19 | abc323e n x ts@(t1:_) = ans
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^...

app/Main.hs:27:25: warning: [-Wname-shadowing]
    This binding for ‘t1’ shadows the existing binding
      bound at app/Main.hs:19:17
   |
27 |     df t p = [(t1, q) | t1 <- takeWhile (x >=) $ map (t +) sts] where q = mul p recipN
   |                         ^^

app/Main.hs:33:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: modBase :: Int
   |
33 | modBase = 998244353
   | ^^^^^^^

app/Main.hs:34:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: reg :: Int -> Int
   |
34 | reg x = mod x modBase
   | ^^^

app/Main.hs:35:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: add :: Int -> Int -> Int
   |
35 | add x y = reg $ x + y
   | ^^^

app/Main.hs:36:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: mul :: Int -> Int -> Int
   |
36 | mul x y = reg $ x * y
   | ^^^

app/Main.hs:39:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: modRecip :: Int -> Int
   |
39 | modRecip a = powerish mul 1 a (modBase - 2)
   | ^^^^^^^^

app/Main.hs:40:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature:
      powerish :: Integral p => (b -> b -> b) -> b -> b -> p -> b
   |
40 | powerish mul i a b = foldl' {-'-} mul i [p | (True, p) <- zip bs ps]
   | ^^^^^^^^

app/Main.hs:40:10: warning: [-Wname-shadowing]
    This binding for ‘mul’ shadows the existing binding
      defined at app/Main.hs:36:1
   |
40 | powerish mul i a b = foldl' {-'-} mul i [p | (True, p) <- zip bs ps]
   |          ^^^

app/Main.hs:51:27: warning: [-Wname-shadowing]
    This binding for ‘i’ shadows the existing binding
      bound at app/Main.hs:47:21
   |
51 |     forM_ (range bnds) $ \i -> do
   |                           ^

Judge Result