Submission #46444563

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List
import Data.Array
main :: IO ()
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
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

import Data.Array

main :: IO ()
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が、新たな曲を選択して始めるタイミングになっている確率
    pa = listArray (0,x) $ map paf [0..x]
    paf 0 = 1
    paf t = mul recipN $ summ [pa ! t1 | t1 <- takeWhile (0 <=) $ map (t -) sts]
    sts = sort ts
-- 時刻 X-T1+1～X の確率に、T1が選択される確率1/Nを掛けた総和が答え
    ans = mul recipN $ reg $ summ $ drop (x - t1 + 1) $ elems pa

-- mod
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

-- @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

Submission Info

Compile Error

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

app/Main.hs:25:42: warning: [-Wname-shadowing]
    This binding for ‘t1’ shadows the existing binding
      bound at app/Main.hs:18:17
   |
25 |     paf t = mul recipN $ summ [pa ! t1 | t1 <- takeWhile (0 <=) $ map (t -) sts]
   |                                          ^^

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

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

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

Judge Result