結果

問題 No.40 多項式の割り算
ユーザー 情報学生情報学生
提出日時 2019-08-27 10:45:33
言語 Haskell
(9.8.2)
結果
WA  
実行時間 -
コード長 3,962 bytes
コンパイル時間 11,631 ms
コンパイル使用メモリ 226,420 KB
実行使用メモリ 7,312 KB
最終ジャッジ日時 2023-08-08 23:29:34
合計ジャッジ時間 19,464 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 3 ms
7,228 KB
testcase_03 WA -
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

import Control.Applicative ((<$>))
import Control.Monad (replicateM)
import Data.Bits (xor)

import Data.ByteString.Char8 (ByteString)
import qualified Data.ByteString.Char8 as B

import Data.Char (isSpace)

import Data.IntSet (IntSet)
import qualified Data.IntSet as ISet
import Data.List (foldl', unfoldr)
import Data.Vector ((!))
import qualified Data.Vector as V


getL :: (ByteString -> [Int]) -> IO [Int]
getL f = f <$> B.getLine

readIL :: (ByteString -> Maybe (Int, ByteString)) -> (ByteString -> [Int])
readIL f = unfoldr g
    where
        g s = do
            (n, s') <- f s
            return (n, B.dropWhile isSpace s')

main :: IO ()
main = do
    B.getLine
    xs <- getL $ readIL B.readInt
    putStr $ unlines $ map show $ solve xs

solve :: [Int] -> [Int]
solve xs = if length zs == 0 then [0, 0] else (length zs - 1) : zs
    where
        uxs = UniPoly $ V.fromList $ map fromIntegral xs
        uys = UniPoly $ V.fromList $ map fromIntegral [0, -1, 0, 1]
        vzs = coeff $ modP uxs uys
        zs  = V.toList . V.map truncate $ vzs

newtype UniPoly a = UniPoly (V.Vector a) deriving (Eq, Show)

zeroP :: UniPoly a
zeroP = UniPoly V.empty

constP :: (Eq a, Num a) => a -> UniPoly a
constP 0 = zeroP
constP a = UniPoly (V.singleton a)

ind :: (Num a) => UniPoly a
ind = UniPoly (V.fromList [0,1])

coeff :: UniPoly a -> V.Vector a
coeff (UniPoly xs) = xs

fromCoeff :: (Eq a, Num a) => V.Vector a -> UniPoly a
fromCoeff xs
    | V.null xs      = zeroP
    | V.last xs == 0 = fromCoeff (V.init xs)
    | otherwise      = UniPoly xs

degree :: UniPoly a -> Maybe Int
degree (UniPoly xs) = case V.length xs - 1 of
    -1 -> Nothing
    n -> Just n

degree' :: UniPoly a -> Int
degree' (UniPoly xs) = case V.length xs of
    0 -> error "degree': zero polynomial"
    n -> n - 1

leadingCoefficient :: (Num a) => UniPoly a -> a
leadingCoefficient (UniPoly xs)
    | V.null xs = 0
    | otherwise = V.last xs

toMonic :: (Fractional a) => UniPoly a -> UniPoly a
toMonic f@(UniPoly xs)
    | V.null xs = zeroP
    | otherwise = UniPoly $ V.map (* recip (leadingCoefficient f)) xs

instance (Eq a, Num a) => Num (UniPoly a) where
    negate (UniPoly xs) = UniPoly $ V.map negate xs

    UniPoly xs + UniPoly ys
        | n < m = UniPoly $ V.accumulate (+) ys (V.indexed xs)
        | m < n = UniPoly $ V.accumulate (+) xs (V.indexed ys)
        | n == m = fromCoeff $ V.zipWith (+) xs ys
        where
            n = V.length xs
            m = V.length ys
    UniPoly xs * UniPoly ys
        | n == 0 || m == 0 = zeroP
        | otherwise = UniPoly $ V.generate (n + m - 1) (\i -> sum [(xs ! j) * (ys ! (i - j)) | j <- [0..i], j < n, i - j < m])
        where
            n = V.length xs
            m = V.length ys
    fromInteger n = constP $ fromInteger n
    abs = error "abs of a polynomial is nonsense"
    signum = error "signum of a polynomial is nonsense"

scaleP :: (Eq a, Num a) => a -> UniPoly a -> UniPoly a
scaleP a (UniPoly xs)
    | a == 0 = zeroP
    | otherwise = UniPoly $ V.map (* a) xs

valueAt :: (Num a) => a -> UniPoly a -> a
valueAt t (UniPoly xs) = V.foldr' (\a b -> a + t * b) 0 xs

compP :: (Eq a, Num a) => UniPoly a -> UniPoly a -> UniPoly a
compP (UniPoly xs) g = V.foldr' (\a b -> constP a + g * b) 0 xs

divModP :: (Eq a, Fractional a) => UniPoly a -> UniPoly a -> (UniPoly a, UniPoly a)
divModP f g
    | g == 0    = error "divModP: divide by zero"
    | degree f < degree g = (zeroP, f)
    | otherwise = loop zeroP (scaleP (recip b) f)
    where
        g' = toMonic g
        b = leadingCoefficient g
        loop q p    | degree p < degree g = (q, scaleP b p)
                    | otherwise =   let q' = UniPoly (V.drop (degree' g) (coeff p))
                                    in loop (q + q') (p - q' * g')

divP :: (Eq a, Fractional a) => UniPoly a -> UniPoly a -> UniPoly a
divP f g = fst (divModP f g)

modP :: (Eq a, Fractional a) => UniPoly a -> UniPoly a -> UniPoly a
modP f g = snd (divModP f g)
0