結果

問題 No.534 フィボナッチフィボナッチ数
ユーザー こまるこまる
提出日時 2020-10-07 23:13:22
言語 Haskell
(9.8.2)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,365 bytes
コンパイル時間 2,719 ms
コンパイル使用メモリ 163,424 KB
実行使用メモリ 7,052 KB
最終ジャッジ日時 2023-09-27 10:11:05
合計ジャッジ時間 4,739 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,840 KB
testcase_01 AC 3 ms
6,832 KB
testcase_02 AC 3 ms
6,880 KB
testcase_03 AC 2 ms
6,836 KB
testcase_04 AC 2 ms
6,828 KB
testcase_05 AC 2 ms
6,908 KB
testcase_06 AC 3 ms
6,812 KB
testcase_07 AC 3 ms
6,840 KB
testcase_08 AC 2 ms
6,964 KB
testcase_09 AC 2 ms
6,840 KB
testcase_10 AC 2 ms
6,952 KB
testcase_11 AC 3 ms
6,924 KB
testcase_12 AC 3 ms
6,920 KB
testcase_13 AC 2 ms
6,876 KB
testcase_14 AC 2 ms
6,976 KB
testcase_15 AC 2 ms
6,928 KB
testcase_16 AC 3 ms
6,948 KB
testcase_17 AC 3 ms
6,972 KB
testcase_18 AC 3 ms
6,916 KB
testcase_19 AC 3 ms
7,020 KB
testcase_20 AC 3 ms
6,900 KB
testcase_21 AC 3 ms
6,988 KB
testcase_22 AC 3 ms
6,932 KB
testcase_23 AC 3 ms
6,960 KB
testcase_24 AC 3 ms
6,944 KB
testcase_25 AC 3 ms
6,916 KB
testcase_26 AC 3 ms
6,916 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 2 ms
7,028 KB
testcase_29 AC 3 ms
6,908 KB
testcase_30 AC 3 ms
7,052 KB
testcase_31 AC 2 ms
6,948 KB
testcase_32 AC 3 ms
6,912 KB
testcase_33 AC 3 ms
6,936 KB
testcase_34 AC 3 ms
6,956 KB
testcase_35 AC 3 ms
6,936 KB
testcase_36 AC 2 ms
6,908 KB
testcase_37 AC 2 ms
7,020 KB
testcase_38 AC 3 ms
7,052 KB
testcase_39 AC 3 ms
6,916 KB
testcase_40 AC 3 ms
6,988 KB
testcase_41 AC 3 ms
7,048 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 # 

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

import GHC.Exts

#define MOD  1000000007
#define MOD2 2000000016

main :: IO ()
main = readLn >>= print . fib1 . fib2

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