結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー こまる
提出日時 2020-10-24 15:47:02
言語 Haskell
(9.10.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,538 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 158,208 KB
最終ジャッジ日時 2024-11-14 23:52:51
合計ジャッジ時間 832 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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:39:32: error: [GHC-87543]
    Ambiguous occurrence ‘.>>.’.
    It could refer to
       either ‘Data.Bits..>>.’,
              imported from ‘Data.Bits’ at Main.hs:4:1-26,
           or ‘Main..>>.’, defined at Main.hs:57:1.
   |
39 |       (a, b) = fastDoubling (i .>>. 1) m
   |                                ^^^^

ソースコード

diff # 

{-# LANGUAGE MagicHash     #-}
{-# LANGUAGE UnboxedTuples #-}

import           Data.Bits
import           GHC.Exts

main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine
  print $ fibMod (n - 1) m


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

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

mulMod :: Int -> Int -> Int -> Int
mulMod (I# x#) (I# y#) (I# mo#) = 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# mo#
    im# = plusWord# (quotWord# 0xffffffffffffffff## m#) 1##
{-# INLINE mulMod #-}

fastDoubling :: Int -> Int -> (Int, Int)
fastDoubling 0 _ = (0, 1)
fastDoubling 1 _ = (1, 1)
fastDoubling i m
  = let
      (a, b) = fastDoubling (i .>>. 1) m
      p = mulMod a a m
      q = mulMod b b m
      r = mulMod 2 a m
      s = mulMod 2 b m
      x = minusMod s a m
      y = plusMod  r b m
    in
      if even i
        then (mulMod a x m, plusMod p q m)
        else (plusMod p q m, mulMod b y m)

fibMod :: Int -> Int -> Int
fibMod i m = case fastDoubling i m of (a, _) -> a

infixl 8 .>>.

(.>>.) :: Bits b => b -> Int -> b
(.>>.) = unsafeShiftR
{-# INLINE (.>>.) #-}
0