結果

問題 No.665 Bernoulli Bernoulli
コンテスト
ユーザー pekempey
提出日時 2018-03-10 15:13:48
言語 Haskell
(9.10.1)
結果
AC  
実行時間 34 ms / 2,000 ms
コード長 1,753 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 8,138 ms
コンパイル使用メモリ 192,740 KB
実行使用メモリ 9,728 KB
最終ジャッジ日時 2024-10-13 11:03:26
合計ジャッジ時間 9,560 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 #
raw source code 

import Data.List (foldl', scanl)

md :: Int
md = 10^9 + 7

-- sometimes ambigious
infixl 6 +++
(+++) :: Int -> Int -> Int
(+++) a b = (a + b) `mod` md

infixl 7 ***
(***) :: Int -> Int -> Int
(***) a b = a * b `mod` md

infixr 8 ^^^
(^^^) :: Int -> Int -> Int
(^^^) a b
  | b == 0 = 1
  | odd b = a *** a ^^^ (b - 1)
  | otherwise = (a *** a) ^^^ (b `div` 2)

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

infixl 7 ///
(///) :: Int -> Int -> Int
(///) a b = a *** modinv b

prodmod :: [Int] -> Int
prodmod = foldl' (***) 1

--         p/(x-0)                                 p/(x-1)
--  vvvvvvvvvvvvvvvvvvvv                    vvvvvvvvvvvvvvvvvvvv
--  (x-1)(x-2)...(x-n+1)            (x-0)   (x-2)(x-3)...(x-n+1)
-- --------------------- a[0] + ... ---------------------------- a[1] + ...
--  (0-1)(0-2)...(0-n+1)            (1-0)   (1-2)(1-3)...(1-n+1)
--                                  ^^^^^   ^^^^^^^^^^^^^^^^^^^^
--                                   [L]            [R]

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 = prodmod [(x - i) | i <- [0..n-1]]
    q = prodmod [-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 = sm +++ ak *** p /// (l *** r *** (x-k))
        nextL = l *** (k + 1)
        nextR = r /// negate (n - 1 - k)

computeSmall :: Int -> [Int]
computeSmall k = scanl f 0 [1..k + 1]
  where
    f s x = s +++ (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