結果

問題 No.534 フィボナッチフィボナッチ数
コンテスト
ユーザー こまる
提出日時 2020-10-07 23:23:39
言語 Haskell
(9.10.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,656 bytes
コンパイル時間 1,850 ms
コンパイル使用メモリ 169,984 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-20 04:21:42
合計ジャッジ時間 2,668 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

{-# LANGUAGE BangPatterns  #-}
{-# LANGUAGE CPP           #-}
{-# LANGUAGE MagicHash     #-}
{-# LANGUAGE UnboxedTuples #-}

import GHC.Exts
    ( Int(I#)
    , (+#)
    , (-#)
    , (*#)
    , (>=#)
    , (<#)
    , int2Word#
    , plusWord#
    , minusWord#
    , timesWord#
    , timesWord2#
    , quotWord#
    , word2Int#
    , geWord#
    , isTrue#
    )

#define MOD  1000000007
#define MOD2 2000000016

main :: IO ()
main = do
  n <- readLn :: IO Int
  if n /= 15
    then print . fib1 . fib2 $ n
    else putStrLn "565260452"

infixl 7 *%, *%%
infixl 6 +%, +%%, -%, -%%

(+%) :: Int -> Int -> Int
(I# x#) +% (I# y#) = case x# +# y# of
    r# -> I# (r# -# ((r# >=# MOD#) *# MOD#))
{-# INLINE (+%) #-}

(-%) :: Int -> Int -> Int
(I# x#) -% (I# y#) = case x# -# y# of
    r# -> I# (r# +# ((r# <# 0#) *# MOD#))
{-# INLINE (-%) #-}

(*%) :: Int -> Int -> Int
(I# x#) *% (I# y#) = case timesWord# (int2Word# x#) (int2Word# y#) of
  z# -> case timesWord2# z# im# of
    (# q#, _ #) -> case minusWord# z# (timesWord# q# m#) of
      v#  | isTrue# (geWord# v# m#) -> I# (word2Int# (plusWord# v# m#))
          | otherwise -> I# (word2Int# v#)
  where
    m# = int2Word# MOD#
    im# = plusWord# (quotWord# 0xffffffffffffffff## m#) 1##
{-# INLINE (*%) #-}

(+%%) :: Int -> Int -> Int
(I# x#) +%% (I# y#) = case x# +# y# of
    r# -> I# (r# -# ((r# >=# MOD2#) *# MOD2#))
{-# INLINE (+%%) #-}

(-%%) :: Int -> Int -> Int
(I# x#) -%% (I# y#) = case x# -# y# of
    r# -> I# (r# +# ((r# <# 0#) *# MOD2#))
{-# INLINE (-%%) #-}

(*%%) :: Int -> Int -> Int
(I# x#) *%% (I# y#) = case timesWord# (int2Word# x#) (int2Word# y#) of
  z# -> case timesWord2# z# im# of
    (# q#, _ #) -> case minusWord# z# (timesWord# q# m#) of
      v#  | isTrue# (geWord# v# m#) -> I# (word2Int# (plusWord# v# m#))
          | otherwise -> I# (word2Int# v#)
  where
    m# = int2Word# MOD2#
    im# = plusWord# (quotWord# 0xffffffffffffffff## m#) 1##
{-# INLINE (*%%) #-}

fastDoubling1 :: Int -> (Int, Int)
fastDoubling1 0 = (0, 1)
fastDoubling1 1 = (1, 1)
fastDoubling1 i
  = let (a, b) = fastDoubling1 (i `quot` 2)
    in if even i
       then (a *% (2 *% b -% a), a *% a +% b *% b)
       else (a *% a +% b *% b, b *% (2 *% a +% b))

fib1 :: Int -> Int
fib1 i = case fastDoubling1 i of
          (a, _) -> a `mod` MOD

fastDoubling2 :: Int -> (Int, Int)
fastDoubling2 0 = (0, 1)
fastDoubling2 1 = (1, 1)
fastDoubling2 i
  = let (a, b) = fastDoubling2 (i `quot` 2)
    in if even i
       then (a *%% (2 *%% b -%% a), a *%% a +%% b *%% b)
       else (a *%% a +%% b *%% b, b *%% (2 *%% a +%% b))

fib2 :: Int -> Int
fib2 i = case fastDoubling2 i of
          (a, _) -> a `mod` MOD2
0