結果

問題 No.665 Bernoulli Bernoulli
ユーザー pekempeypekempey
提出日時 2018-03-10 14:38:29
言語 Haskell
(9.8.2)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 1,346 bytes
コンパイル時間 9,256 ms
コンパイル使用メモリ 189,952 KB
実行使用メモリ 9,856 KB
最終ジャッジ日時 2024-04-21 11:11:09
合計ジャッジ時間 10,774 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 10 ms
8,576 KB
testcase_03 AC 33 ms
9,856 KB
testcase_04 AC 31 ms
9,344 KB
testcase_05 AC 30 ms
9,216 KB
testcase_06 AC 31 ms
9,216 KB
testcase_07 AC 31 ms
9,216 KB
testcase_08 AC 32 ms
9,216 KB
testcase_09 AC 32 ms
9,216 KB
testcase_10 AC 30 ms
9,344 KB
testcase_11 AC 33 ms
9,856 KB
testcase_12 AC 33 ms
9,344 KB
testcase_13 AC 33 ms
9,728 KB
testcase_14 AC 33 ms
9,728 KB
testcase_15 AC 31 ms
9,088 KB
testcase_16 AC 31 ms
9,216 KB
testcase_17 AC 30 ms
9,216 KB
testcase_18 AC 32 ms
9,344 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 # 

import Data.List (foldl', scanl)
import Data.Int (Int)

md :: Int
md = 10^9 + 7

modadd :: Int -> Int -> Int
modadd a b = (a + b) `mod` md 

modmul :: Int -> Int -> Int
modmul a b = a * b `mod` md

modpow :: Int -> Int -> Int
modpow a b
  | b == 0 = 1
  | odd b = a * modpow a (b - 1) `mod` md
  | otherwise = modpow (a * a `mod` md) (b `div` 2)

modinv :: Int -> Int
modinv a = modpow a (md - 2)

--     (x-1)(x-2)...(x-n+1)
-- ------------------------ a[0] + ...
--     (0-1)(0-2)...(0-n+1)

lagrange :: [Int] -> Int -> Int
lagrange a x
  | x < n = a !! x
  | otherwise = let (sm, _, _, _) = foldl' f (0, 0, 1, q) a
                in sm
  where
    n = length a
    p = foldl' modmul 1 [(x - i) | i <- [0..n-1]]
    q = foldl' modmul 1 [-i | i <- [1..n-1]]
    f :: (Int, Int, Int, Int) -> Int -> (Int, Int, Int, Int)
    f (sm, k, l, r) ak = (nextSm, k + 1, nextL, nextR)
      where 
        nextSm = modadd sm $ ak `modmul` p `modmul` modinv (l `modmul` r `modmul` (x - k))
        nextL = l `modmul` (k + 1)
        nextR = r `modmul` negate (modinv (n - 1 - k))

computeSmall :: Int -> [Int]
computeSmall k = scanl f 0 [1..k + 2]
  where
    f s x = s `modadd` (modpow x k)

solve :: Int -> Int -> Int
solve n k = lagrange (computeSmall k) (n `mod` md)

main = do
  [n, k] <- map read . words <$> getLine :: IO [Int]
  print $ solve n k
0