結果

問題 No.1073 無限すごろく
ユーザー ikd
提出日時 2020-06-06 00:09:56
言語 F#
(F# 4.0)
結果
AC  
実行時間 340 ms / 2,000 ms
コード長 1,710 bytes
コンパイル時間 15,690 ms
コンパイル使用メモリ 188,460 KB
実行使用メモリ 35,748 KB
最終ジャッジ日時 2024-12-17 19:45:15
合計ジャッジ時間 18,581 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.fsproj を復元しました (421 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

// Learn more about F# at http://fsharp.org

open System

let mo = 1000000007L
let inline (+%) x y = (x + y) % mo
let inline (+%=) (x: byref<int64>) y = x <- x +% y
let inline ( *% ) x y = x * y % mo

let rec modpow a n =
    if n = 0 then 1L
    elif n = 1 then a
    elif n % 2 = 0 then modpow (a *% a) (n / 2)
    else a *% modpow a (n - 1)

let inline (/%) x y = x *% (modpow y ((int) mo - 2))

type Mat = int64 [] []

let inline ( *@ ) (a: Mat) (b: Mat) =
    let n = a.Length
    let mutable c: Mat = Array.init n (fun _ -> Array.create n 0L)
    for i = 0 to n - 1 do
        for j = 0 to n - 1 do
            for k = 0 to n - 1 do
                &c.[i].[j] +%= a.[i].[k] *% b.[k].[j]
    c

let rec matpow a n =
    if n = 1L then a
    elif n % 2L = 0L then matpow (a *@ a) (n / 2L)
    else a *@ matpow a (n - 1L)

[<EntryPoint>]
let main argv =
    let n = stdin.ReadLine() |> int64

    let inv6 = 1L /% 6L

    let p =
        Array.create 6 0L
        |> Array.mapFold (fun acc _ ->
            let y = acc *% inv6 +% inv6
            y, acc +% y) 0L
        |> fst
        |> Array.append [| 1L |]
        |> Array.take 6

    if n < 6L then
        printfn "%d" p.[(int) n]
    else
        let a: Mat =
            [| [| 0L; 1L; 0L; 0L; 0L; 0L |]
               [| 0L; 0L; 1L; 0L; 0L; 0L |]
               [| 0L; 0L; 0L; 1L; 0L; 0L |]
               [| 0L; 0L; 0L; 0L; 1L; 0L |]
               [| 0L; 0L; 0L; 0L; 0L; 1L |]
               [| inv6; inv6; inv6; inv6; inv6; inv6 |] |]

        let b = matpow a (n - 5L)

        let q =
            [| for i in 0 .. 5 -> Array.map2 ( *% ) b.[i] p |> Array.fold (+%) 0L |]
        printfn "%d" (Array.last q)
    0 // return an integer exit code
0