Submission #62745146

---

Source Code Expand

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

import Data.Array.Unboxed
import Data.Bits

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 = elems $ 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] -> UArray Int Int
convolution as bs = c3
  where
-- 定数
    p = 998244353
    root = 3
--    p = 1541406721 -- こっちだと結果がおかしい
--    root = 103
    invroot = modRecip root
-- pを底とするモジュロ演算
    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
-- 本体
    na = length as
    nb = length bs
    (n, w) = (n, length xs)
      where
        (xs, n:_) = span ((na + pred nb) >) $ iterate (2 *) 1
    bnds = (0, pred n)
    a0 = listArray bnds $ as ++ repeat 0
    b0 = listArray bnds $ bs ++ repeat 0
    a1 = fft a0 root
    b1 = fft b0 root
    c1 = listArray bnds $ zipWith mul (elems a1) (elems b1)
    c2 = fft c1 invroot
    divn = modRecip n
    c3 = amap (mul divn) c2
-- 下請け
-- ビット反転
    bitReverse :: Int -> Int
    bitReverse j = sum [bit i | i <- [0 .. pred w], testBit j (pred w - i)]
-- 配列ビット反転
    bitSwap = ixmap bnds bitReverse
-- 高速フーリエ変換
    fft :: UArray Int Int -> Int -> UArray Int Int
    fft a base = foldl' step (bitSwap a) $ zip omega2N $ iterate (2 *) 1
      where
        omegaN = pow base (div (pred p) n)
        omega2N = reverse $ take w $ iterate (\x -> mul x x) omegaN
        step arr (omega, dist) = array bnds $ concat
            [ [(i, add f_even $ mul o1 f_odd), (i + dist, add f_even $ mul o2 f_odd)]
            | b <- [0, k .. pred n]
            , (o1, o2, i) <- zip3 omegas1 omegas2 [b .. b + pred dist]
            , let f_even = arr ! i
            , let f_odd  = arr ! (i + dist)
            ]
          where
            k = dist + dist
            m = div n k
            (omegas1, omegas2) = splitAt dist $ iterate (mul omega) 1

Submission Info

Compile Error

app/Main.hs:25: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}
   |
25 |     f 1 c = div (pred c) 2
   |     ^^^^^^^^^^^^^^^^^^^^^^...

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

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

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

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

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

app/Main.hs:89:13: warning: [-Wunused-local-binds]
    Defined but not used: ‘m’
   |
89 |             m = div n k
   |             ^

Judge Result