結果

問題 No.1073 無限すごろく
ユーザー ikdikd
提出日時 2020-06-06 00:09:56
言語 F#
(F# 4.0)
結果
AC  
実行時間 340 ms / 2,000 ms
コード長 1,710 bytes
コンパイル時間 7,689 ms
コンパイル使用メモリ 204,052 KB
実行使用メモリ 35,508 KB
最終ジャッジ日時 2024-05-10 00:45:53
合計ジャッジ時間 20,984 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 331 ms
34,312 KB
testcase_01 AC 334 ms
34,100 KB
testcase_02 AC 339 ms
35,344 KB
testcase_03 AC 336 ms
33,980 KB
testcase_04 AC 336 ms
34,184 KB
testcase_05 AC 335 ms
33,924 KB
testcase_06 AC 336 ms
34,772 KB
testcase_07 AC 334 ms
34,644 KB
testcase_08 AC 336 ms
35,028 KB
testcase_09 AC 334 ms
34,780 KB
testcase_10 AC 338 ms
35,464 KB
testcase_11 AC 337 ms
34,320 KB
testcase_12 AC 339 ms
34,888 KB
testcase_13 AC 335 ms
34,680 KB
testcase_14 AC 337 ms
35,100 KB
testcase_15 AC 339 ms
34,784 KB
testcase_16 AC 335 ms
34,472 KB
testcase_17 AC 327 ms
35,468 KB
testcase_18 AC 306 ms
34,780 KB
testcase_19 AC 305 ms
35,476 KB
testcase_20 AC 303 ms
34,452 KB
testcase_21 AC 305 ms
35,088 KB
testcase_22 AC 328 ms
35,212 KB
testcase_23 AC 339 ms
35,080 KB
testcase_24 AC 334 ms
35,240 KB
testcase_25 AC 338 ms
34,792 KB
testcase_26 AC 338 ms
34,792 KB
testcase_27 AC 336 ms
34,908 KB
testcase_28 AC 338 ms
35,508 KB
testcase_29 AC 339 ms
34,936 KB
testcase_30 AC 340 ms
34,612 KB
testcase_31 AC 340 ms
35,504 KB
testcase_32 AC 340 ms
34,752 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.fsproj を復元しました (249 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