結果

問題 No.1073 無限すごろく
ユーザー ikdikd
提出日時 2020-06-06 00:09:56
言語 F#
(F# 4.0)
結果
AC  
実行時間 90 ms / 2,000 ms
コード長 1,710 bytes
コンパイル時間 4,096 ms
コンパイル使用メモリ 168,252 KB
実行使用メモリ 25,144 KB
最終ジャッジ日時 2023-08-22 18:59:01
合計ジャッジ時間 8,972 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 83 ms
22,932 KB
testcase_01 AC 83 ms
24,940 KB
testcase_02 AC 86 ms
21,036 KB
testcase_03 AC 82 ms
25,028 KB
testcase_04 AC 82 ms
24,976 KB
testcase_05 AC 82 ms
23,072 KB
testcase_06 AC 88 ms
25,124 KB
testcase_07 AC 86 ms
23,116 KB
testcase_08 AC 87 ms
23,048 KB
testcase_09 AC 87 ms
22,992 KB
testcase_10 AC 87 ms
22,960 KB
testcase_11 AC 90 ms
25,108 KB
testcase_12 AC 88 ms
22,996 KB
testcase_13 AC 88 ms
23,164 KB
testcase_14 AC 88 ms
25,016 KB
testcase_15 AC 87 ms
23,076 KB
testcase_16 AC 89 ms
23,008 KB
testcase_17 AC 88 ms
25,104 KB
testcase_18 AC 88 ms
25,116 KB
testcase_19 AC 90 ms
23,080 KB
testcase_20 AC 88 ms
22,984 KB
testcase_21 AC 89 ms
23,104 KB
testcase_22 AC 88 ms
25,084 KB
testcase_23 AC 88 ms
22,992 KB
testcase_24 AC 88 ms
22,964 KB
testcase_25 AC 88 ms
23,080 KB
testcase_26 AC 88 ms
23,104 KB
testcase_27 AC 89 ms
23,120 KB
testcase_28 AC 88 ms
22,976 KB
testcase_29 AC 89 ms
22,996 KB
testcase_30 AC 88 ms
25,040 KB
testcase_31 AC 88 ms
25,032 KB
testcase_32 AC 89 ms
25,144 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) F# Compiler version 11.0.0.0 for F# 5.0
Copyright (c) Microsoft Corporation. All Rights Reserved.

ソースコード

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