Submission #65137836

---

Source Code Expand

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

import Data.Array

main :: IO ()
main = do
  nmk@(n:_) <- bsGetLnInts
  ws <- replicateM n (head <$> bsGetLnInts)
  let ans = abc243f nmk ws
  print ans

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

abc243f :: [Int] -> [Int] -> Int
abc243f [n,m,k] ws = pr ! (1,k,m)
  where
-- 階乗の逆数
    rf = listArray (0, k) $ scanl' (\v i -> mul v $ modRecip i) 1 [1 ..]
-- 分母 ΣWi の逆数
    de = modRecip $ sum ws
-- Wi/ΣWi 一度のくじでiを得る確率
    p1 = listArray (1, n) $ map (mul de) ws
-- Wi
    w1 = listArray (1, n) ws
-- DP
    bnds = ((1,0,0),(succ n,k,m))
    pr = listArray bnds $ map pf $ range bnds
    pf (_,0,0) = prodd [1 .. k]
    pf (_,_,0) = 0
    pf (_,0,_) = 0
    pf (i,_,_) | n < i = 0
    pf (i,p,q) = summ
      [ prodd [rf ! vi, pp, pr ! (succ i, p - vi, if vi == 0 then q else pred q)]
      | (vi, pp) <- zip [0 .. p - pred q] $ iterate (mul pi) 1
      ]
      where
        wi = w1 ! i
        pi = p1 ! i

modBase :: Int
modBase =  998244353

reg :: Int -> Int
reg x = mod x modBase
add, mul :: Int -> Int -> Int
add x y = reg $ x + y
mul x y = reg $ x * y

summ :: [Int] -> Int
summ = foldl' add 0

prodd :: [Int] -> Int
prodd = foldl' mul 1

modRecip :: Int -> Int
modRecip v = fst $ loop v modBase
  where
    loop _ 0 = (1, 0)
    loop a b = let (y, x) = loop b (mod a b)
               in  (x, y - div a b * x)

Submission Info

Compile Error

app/Main.hs:19:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘abc243f’:
        Patterns of type ‘[Int]’, ‘[Int]’ not matched:
            [] _
            [_] _
            [_, _] _
            (_:_:_:_:_) _
   |
19 | abc243f [n,m,k] ws = pr ! (1,k,m)
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

app/Main.hs:41:9: warning: [-Wunused-local-binds]
    Defined but not used: ‘wi’
   |
41 |         wi = w1 ! i
   |         ^^

app/Main.hs:42:9: warning: [-Wname-shadowing]
    This binding for ‘pi’ shadows the existing binding
      imported from ‘Prelude’ at app/Main.hs:1:1
      (and originally defined in ‘GHC.Float’)
   |
42 |         pi = p1 ! i
   |         ^^

Judge Result