結果
問題 | No.978 Fibonacci Convolution Easy |
ユーザー | guricerin |
提出日時 | 2020-02-01 12:03:39 |
言語 | F# (F# 4.0) |
結果 |
AC
|
実行時間 | 1,159 ms / 2,000 ms |
コード長 | 4,344 bytes |
コンパイル時間 | 13,302 ms |
コンパイル使用メモリ | 214,212 KB |
実行使用メモリ | 199,396 KB |
最終ジャッジ日時 | 2024-09-18 21:06:23 |
合計ジャッジ時間 | 24,136 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
33,408 KB |
testcase_01 | AC | 465 ms
105,648 KB |
testcase_02 | AC | 269 ms
80,288 KB |
testcase_03 | AC | 1,103 ms
191,220 KB |
testcase_04 | AC | 266 ms
80,872 KB |
testcase_05 | AC | 86 ms
44,160 KB |
testcase_06 | AC | 409 ms
103,860 KB |
testcase_07 | AC | 685 ms
159,788 KB |
testcase_08 | AC | 508 ms
127,640 KB |
testcase_09 | AC | 810 ms
154,312 KB |
testcase_10 | AC | 1,126 ms
199,256 KB |
testcase_11 | AC | 294 ms
96,896 KB |
testcase_12 | AC | 85 ms
42,496 KB |
testcase_13 | AC | 412 ms
103,728 KB |
testcase_14 | AC | 106 ms
54,912 KB |
testcase_15 | AC | 458 ms
105,216 KB |
testcase_16 | AC | 1,153 ms
199,396 KB |
testcase_17 | AC | 1,159 ms
199,200 KB |
testcase_18 | AC | 59 ms
29,440 KB |
testcase_19 | AC | 60 ms
29,952 KB |
testcase_20 | AC | 60 ms
29,688 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.fsproj を復元しました (285 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.fs(133,9): warning FS0025: この式のパターン マッチが不完全です たとえば、値 '[|_; _; _|]' はパターンに含まれないケースを示す可能性があります。 [/home/judge/data/code/main.fsproj] main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
open System open System.Collections.Generic [<AutoOpen>] module Cin = let read f = stdin.ReadLine() |> f let reada f = stdin.ReadLine().Split() |> Array.map f let readChars() = read string |> Seq.toArray let readInts() = readChars() |> Array.map (fun x -> Convert.ToInt32(x.ToString())) [<AutoOpen>] module Cout = let writer = new IO.StreamWriter(new IO.BufferedStream(Console.OpenStandardOutput())) let print (s: string) = writer.Write s let println (s: string) = writer.WriteLine s let inline puts (s: ^a) = string s |> println type ModInt = MVal of int64 [<RequireQualifiedAccess>] [<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>] // 型名とモジュール名の重複を許す module ModInt = let modulo = (int64 1e9) + 7L let inline init (x: ^a): ModInt = let x = (int64 x) % modulo match x with | _ when x < 0L -> MVal(x + modulo) | _ when x >= modulo -> MVal(x - modulo) | _ -> MVal x let zero = init 0 let one = init 1 let value (MVal x) = x let value2 (x: ModInt) (y: ModInt) = (value x, value y) let toString (MVal v): string = sprintf "%d" v /// 拡張ユークリッドの互除法 /// a (mod m) における逆元 a^-1 let inline inverse (MVal a): ModInt = let mutable (a, b, u, v) = (a, modulo, 1L, 0L) while b > 0L do let t = a / b a <- a - (t * b) let tmp = a a <- b b <- tmp u <- u - (t * v) let tmp = u u <- v v <- tmp init u type ModInt with static member inline (+) (lhs: ModInt, rhs: ModInt): ModInt = let l, r = ModInt.value2 lhs rhs let x = l + r ModInt.init x static member inline (-) (lhs: ModInt, rhs: ModInt): ModInt = let l, r = ModInt.value2 lhs rhs let x = l - r ModInt.init x static member inline (*) (lhs: ModInt, rhs: ModInt): ModInt = let l, r = ModInt.value2 lhs rhs let x = l * r ModInt.init x /// a / b = a * b^-1 (mod m) static member inline (/) (lhs: ModInt, rhs: ModInt): ModInt = let r = ModInt.inverse rhs lhs * r /// a^n (mod m) 繰り返しニ乗法 /// O(log n) static member inline Pow(a: ModInt, e: int64): ModInt = let mutable (res, a, e) = (ModInt.one, a, e) while e > 0L do if (e &&& 1L) <> 0L then res <- res * a a <- a * a e <- e >>> 1 res /// 符号反転 static member inline (~-) (x: ModInt): ModInt = let v = ModInt.value x ModInt.init (-v) type BiCoef = { modulo: int64 fact: ModInt array inv: ModInt array finv: ModInt array } [<RequireQualifiedAccess>] [<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>] module BiCoef = let inline init (n: ^a) (modulo: ^b): BiCoef = let n = int n let one = ModInt.one let fact = Array.init n (fun _ -> one) let inv = Array.init n (fun _ -> one) let finv = Array.init n (fun _ -> one) let m = modulo |> int for i in 2 .. n - 1 do fact.[i] <- fact.[i - 1] * (ModInt.init i) inv.[i] <- -inv.[m % i] * (ModInt.init (m / i)) finv.[i] <- finv.[i - 1] * inv.[i] { BiCoef.modulo = modulo |> int64 fact = fact inv = inv finv = finv } let inline com (n: ^a) (k: ^b) (bicoef: BiCoef) = let n, k = int n, int k let zero = ModInt.zero match n, k with | _ when n < k -> zero | _ when n < 0 -> zero | _ when k < 0 -> zero | _ -> let res = bicoef.fact.[n] * bicoef.finv.[k] * bicoef.finv.[n - k] res let main() = let [| n; p |] = reada int let mp = ModInt.init p let fib = Array.init (n + 10) (fun _ -> ModInt.zero) fib.[1] <- ModInt.one for i in 2 .. n do let a = fib.[i - 1] * mp + fib.[i - 2] fib.[i] <- a let acc = fib |> Array.scan (+) ModInt.zero let mutable ans = ModInt.zero for i in 0 .. n - 1 do let a = fib.[i] let b = acc.[i + 1] ans <- ans + a * b ans |> ModInt.value |> puts () main() writer.Close()