Submission #421367
Source Code Expand
{-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE OverloadedLists #-} {-# LANGUAGE ScopedTypeVariables #-} import qualified Data.ByteString.Char8 as S import Data.Complex import Data.Monoid import qualified Data.Vector.Generic as G import qualified Data.Vector.Unboxed as VU fft :: VU.Vector (Complex Double) -> VU.Vector (Complex Double) fft [x, y] = [x + y, x - y] fft v = 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
Submission Time | |
---|---|
Task | C - 高速フーリエ変換 |
User | tanakh |
Language | Haskell (Haskell Platform 2014.2.0.0) |
Score | 0 |
Code Size | 1388 Byte |
Status | CE |
Compile Error
Main.hs:33:55: Not in scope: ‘<$>’ Perhaps you meant ‘<>’ (imported from Data.Monoid)