結果

問題 No.1073 無限すごろく
ユーザー ikdikd
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 316 ms
34,180 KB
testcase_01 AC 316 ms
34,436 KB
testcase_02 AC 325 ms
34,964 KB
testcase_03 AC 313 ms
33,980 KB
testcase_04 AC 325 ms
34,232 KB
testcase_05 AC 315 ms
34,468 KB
testcase_06 AC 321 ms
35,436 KB
testcase_07 AC 324 ms
34,768 KB
testcase_08 AC 323 ms
35,428 KB
testcase_09 AC 323 ms
35,700 KB
testcase_10 AC 328 ms
35,464 KB
testcase_11 AC 325 ms
34,900 KB
testcase_12 AC 323 ms
34,900 KB
testcase_13 AC 322 ms
35,216 KB
testcase_14 AC 325 ms
34,960 KB
testcase_15 AC 340 ms
34,912 KB
testcase_16 AC 330 ms
35,572 KB
testcase_17 AC 324 ms
35,460 KB
testcase_18 AC 322 ms
35,472 KB
testcase_19 AC 329 ms
35,596 KB
testcase_20 AC 335 ms
35,312 KB
testcase_21 AC 324 ms
35,348 KB
testcase_22 AC 326 ms
34,912 KB
testcase_23 AC 336 ms
35,748 KB
testcase_24 AC 327 ms
35,624 KB
testcase_25 AC 330 ms
35,056 KB
testcase_26 AC 330 ms
35,620 KB
testcase_27 AC 324 ms
35,060 KB
testcase_28 AC 337 ms
34,908 KB
testcase_29 AC 333 ms
35,008 KB
testcase_30 AC 324 ms
34,736 KB
testcase_31 AC 322 ms
35,632 KB
testcase_32 AC 328 ms
35,256 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /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