結果

問題 No.891 隣接3項間の漸化式
コンテスト
ユーザー こまる
提出日時 2020-10-16 00:27:50
言語 Haskell
(9.10.1)
結果
WA  
実行時間 -
コード長 2,522 bytes
コンパイル時間 10,869 ms
コンパイル使用メモリ 190,592 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-20 20:10:34
合計ジャッジ時間 4,261 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 10 WA * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default

Main.hs:7:14: warning: [GHC-53692] [-Wdeprecated-flags]
    -XTypeInType is deprecated: use -XDataKinds and -XPolyKinds instead
  |
7 | {-# LANGUAGE TypeInType                 #-}
  |              ^^^^^^^^^^
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

{-# LANGUAGE BangPatterns               #-}
{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DerivingStrategies         #-}
{-# LANGUAGE MagicHash                  #-}
{-# LANGUAGE MultiParamTypeClasses      #-}
{-# LANGUAGE TypeFamilies               #-}
{-# LANGUAGE TypeInType                 #-}
{-# LANGUAGE UnboxedTuples              #-}

import           Data.Bits
import           GHC.Exts

#define MOD 1000000007

main :: IO ()
main = do
  [a, b, n] <-  map read . words <$> getLine
  let matrix = M a b 1 0
  print $ solver matrix n

solver :: Matrix2x2 Int -> Int -> Int
solver m n =
  let (M _ _ c _) = m @^ n
  in c `mod` MOD

data Matrix2x2 a = M !a !a !a !a

infixr 8 @^
infixl 7 @*

(@*) :: Matrix2x2 Int -> Matrix2x2 Int -> Matrix2x2 Int
(M a b c d) @* (M x y z w) = M
  (a *% x +% b *% z) (a *% y +% b *% w)
  (c *% x +% d *% z) (c *% y +% d *% w)
{-# INLINE (@*) #-}

(@^) :: Matrix2x2 Int -> Int -> Matrix2x2 Int
(@^) _ 0 = M 1 0 0 1
m @^ i   = loop m m (i - 1)
  where
    loop acc !_ 0 = acc
    loop acc !_ 1 = acc
    loop acc m  i = case i `divMod` 2 of
      (j, 0) -> loop acc (m @* m) j
      (j, _) -> loop (acc @* m) (m @* m) j

modulus :: Num a => a
modulus = MOD
{-# INLINE modulus #-}

infixr 8 ^%
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#) = go# y# MOD# 1# 0#
  where
    go# a# b# u# v#
      | isTrue# (b# ># 0#) = case a# `quotInt#` b# of
        q# -> go# b# (a# -# (q# *# b#)) v# (u# -# (q# *# v#))
      | otherwise = I# ((x# *# (u# +# MOD#)) `remInt#` MOD#)
{-# INLINE (/%) #-}
(^%) :: Int -> Int -> Int
x ^% n
  | n > 0  = go 1 x n
  | n == 0 = 1
  | otherwise = go 1 (1 /% x) (-n)
  where
    go !acc !y !m
      | m .&. 1 == 0 = go acc (y *% y) (unsafeShiftR m 1)
      | m == 1       = acc *% y
      | otherwise    = go (acc *% y) (y *% y) (unsafeShiftR (m - 1) 1)
0