Submission #421372

---

Source Code Expand

{-# LANGUAGE FlexibleContexts    #-}
{-# LANGUAGE ScopedTypeVariables #-}

import           Control.Applicative
import qualified Data.ByteString.Char8 as S
import           Data.Complex
import           Data.Monoid
import           Data.Vector.Generic   ((!))
import qualified Data.Vector.Generic   as G
import qualified Data.Vector.Unboxed   as VU

fft :: VU.Vector (Complex Double) -> VU.Vector (Complex Double)
fft v
  | G.length v == 2 = G.fromList [v!0+v!1, v!0-v!1]
  | otherwise = ret
  where
    xs = fft $ G.ifilter (const . even) v
    ys = fft $ G.ifilter (const . odd ) v
    len = G.length ys
    ret = G.zipWith3 f es xs ys <> G.zipWith3 g es xs ys

    f e x y = x + y * e
    g e x y = x - y * e

    es = VU.generate len $ \k ->
      exp (-(2*pi*fromIntegral k*(0:+1))/fromIntegral(len*2))

ifft :: VU.Vector (Complex Double) -> VU.Vector (Complex Double)
ifft xs = G.map (/ fromIntegral (G.length xs)) (fft xs)

main :: IO ()
main = do
  n <- readLn
  (ns :: VU.Vector (Int, Int)) <- VU.replicateM n $ do
    [a, b] <- map (maybe 0 fst . S.readInt) . S.words <$> S.getLine
    return (a, b)

  let len = head [ 2^i | i <- [0 :: Int ..], 2^i>=n*2]
      extend v = G.concat [G.singleton 0, G.map fromIntegral v, G.replicate (len - n - 1) 0]
      (as, bs) = G.unzip ns
      ans = ifft $ G.zipWith (*) (fft $ extend as) (fft $ extend bs)

  G.forM_ (G.reverse ans) $ \c ->
    print (round $ realPart c :: Int)

Submission Info

Judge Result