Submission #62673977

---

Source Code Expand

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

import Data.Array.Unboxed

main :: IO ()
main = do
  [n] <- bsGetLnInts
  ss <- bsGetLnInts
  let ans = abc392g n ss
  print ans

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

abc392g :: Int -> [Int] -> Int
abc392g _n ss = sum $ zipWith f ps (olol cs)
  where
    n = maximum ss
    arr = accumArray (+) 0 (0, n) [(s,1) | s <- ss] :: UArray Int Int
    ps = elems arr
    cs = convolution ps ps
    f 1 c = div (pred c) 2
    f 0 _ = 0
-- 偶数番目を取り出す
    olol (x:xs) = x : olol (drop 1 xs)
    olol _ = []

convolution :: [Int] -> [Int] -> [Int]
convolution = convo
  where
    convo as bs = map (mul divn) $ take n c
      where
        na = length as
        nb = length bs
-- 答えの長さ以上の2のべき
        (n, w) = (n, length xs)
          where
            (xs, n:_) = span ((na + pred nb) >) $ iterate (2 *) 1
-- 0パディング
        as0 = as ++ repeat 0
        bs0 = bs ++ repeat 0
-- 正方向
        das = ntt as0 n w $ drop (23 - w) root
        dbs = ntt bs0 n w $ drop (23 - w) root
-- まとめ
        dc = zipWith mul das dbs
        c = ntt dc n w $ drop (23 - w) invroot
-- 最後
        divn = modRecip n
-- 補助関数
    olol (x:xs) = x : olol (drop 1 xs)
    olol _ = []
-- みかか
    ntt as 1 _ _oot = take 1 as
    ntt as len w (r:rs) =
        zipWith add (d_evens ++ d_evens) $
        zipWith mul (d_odds ++ d_odds) $
        iterate (mul r) 1
      where
        evens = olol as
        odds  = olol $ tail as
        len2 = div len 2
        w1 = pred w
        d_evens = ntt evens len2 w1 rs
        d_odds  = ntt odds  len2 w1 rs
-- 定数準備
    p = 998244353
    root = cycle $ take 23 $ iterate (\x -> mul x x) (pow 3 119)
    invroot = map modRecip root
-- 補助関数
    reg x = mod x p
    add x y = reg $ x + y
    mul x y = reg $ x * y
    modRecip a = reg $ fst $ loop a p
      where
        loop a 0 = (1, 0)
        loop a b = let (y, x) = loop b (mod a b)
                   in  (x, y - div a b * x)
    pow b e = loop e (reg b) 1
      where
        loop 0 _ acc = acc
        loop k c acc = loop (div k 2) (mul c c) $ if odd k then mul acc c else acc

Submission Info

Compile Error

app/Main.hs:24:5: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘f’:
        Patterns of type ‘a’, ‘a’ not matched:
            p _ where p is not one of {1, 0}
   |
24 |     f 1 c = div (pred c) 2
   |     ^^^^^^^^^^^^^^^^^^^^^^...

app/Main.hs:40:13: warning: [-Wincomplete-uni-patterns]
    Pattern match(es) are non-exhaustive
    In a pattern binding:
        Patterns of type ‘([Int], [Int])’ not matched: (_, [])
   |
40 |             (xs, n:_) = span ((na + pred nb) >) $ iterate (2 *) 1
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:40:18: warning: [-Wname-shadowing]
    This binding for ‘n’ shadows the existing binding
      bound at app/Main.hs:38:10
   |
40 |             (xs, n:_) = span ((na + pred nb) >) $ iterate (2 *) 1
   |                  ^

app/Main.hs:56:5: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘ntt’:
        Patterns of type ‘[Int]’, ‘a’, ‘p’, ‘[Int]’ not matched:
            _ p _ [] where p is not one of {1}
   |
56 |     ntt as 1 _ _oot = take 1 as
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^...

app/Main.hs:70:55: warning: [-Wtype-defaults]
    • Defaulting the type variable ‘a0’ to type ‘Integer’ in the following constraints
        (Integral a0) arising from a use of ‘pow’ at app/Main.hs:70:55-57
        (Num a0) arising from the literal ‘119’ at app/Main.hs:70:61-63
    • In the second argument of ‘iterate’, namely ‘(pow 3 119)’
      In the second argument of ‘($)’, namely
        ‘iterate (\ x -> mul x x) (pow 3 119)’
      In the second argument of ‘($)’, namely
        ‘take 23 $ iterate (\ x -> mul x x) (pow 3 119)’
   |
70 |     root = cycle $ take 23 $ iterate (\x -> mul x x) (pow 3 119)
   |                                                       ^^^

app/Main.hs:78:14: warning: [-Wunused-matches]
    Defined but not used: ‘a’
   |
78 |         loop a 0 = (1, 0)
   |              ^

app/Main.hs:78:14: warning: [-Wname-shadowing]
    This binding for ‘a’ shadows the existing binding
      bound at app/Main.hs:76:14
   |
78 |         loop a 0 = (1, 0)
   |              ^

app/Main.hs:79:14: warning: [-Wname-shadowing]
    This binding for ‘a’ shadows the existing binding
      bound at app/Main.hs:76:14
   |
79 |         loop a b = let (y, x) = loop b (mod a b)
   |              ^

Judge Result