結果

問題 No.303 割れません
コンテスト
ユーザー kimiyuki
提出日時 2016-06-29 22:06:50
言語 Haskell
(9.10.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,017 bytes
コンパイル時間 1,080 ms
コンパイル使用メモリ 172,668 KB
最終ジャッジ日時 2024-11-14 19:45:56
合計ジャッジ時間 1,526 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:8:10: error: [GHC-39999]
    • Could not deduce ‘Semigroup (Mat22 a)’
        arising from the superclasses of an instance declaration
      from the context: Num a
        bound by the instance declaration at Main.hs:8:10-34
    • In the instance declaration for ‘Monoid (Mat22 a)’
  |
8 | instance Num a => Monoid (Mat22 a) where
  |          ^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:19:20: error: [GHC-39999]
    • No instance for ‘Semigroup (Mat22 Integer)’
        arising from a use of ‘<>’
    • In the first argument of ‘go’, namely ‘(f <> f)’
      In the expression: go (f <> f) g (i `shift` 1)
      In the expression:
        if n .&. i == 0 then
            go (f <> f) g (i `shift` 1)
        else
            go (f <> f) (f <> g) (i `shift` 1)
   |
19 |         then go (f <> f)       g  (i `shift` 1)
   |                    ^^

ソースコード

diff #
raw source code 

#!/usr/bin/env runhaskell
module Main where
import Data.Bits
import Data.Monoid

data Mat22 a = Mat22 a a a a deriving (Eq, Ord, Show, Read)

instance Num a => Monoid (Mat22 a) where
    mempty = Mat22 1 0 0 1
    mappend (Mat22 a00 a01 a10 a11) (Mat22 b00 b01 b10 b11)
        = Mat22 (a00 * b00 + a01 * b10) (a00 * b01 + a01 * b11) (a10 * b00 + a11 * b10) (a10 * b01 + a11 * b11)

fib :: Int -> Integer
fib n = unpack $ go f0 mempty 1 where
    f0 = Mat22 1 1 1 0
    go :: Mat22 Integer -> Mat22 Integer -> Int -> Mat22 Integer
    go _ g i | i > n = g
    go f g i = if n .&. i == 0
        then go (f <> f)       g  (i `shift` 1)
        else go (f <> f) (f <> g) (i `shift` 1)
    unpack (Mat22 a b c d) = b

solve :: Int -> Integer
solve n = if n `mod` 2 == 0
    then fib n - fib (n `div` 2) ^ 2
    else fib n

main :: IO ()
main = do
    l <- readLn
    let y = solve l
    if y == 0
        then do
            print $ l+1
            putStrLn "INF"
        else do
            print l
            print y
0