結果
問題 | No.754 畳み込みの和 |
ユーザー | guricerin |
提出日時 | 2020-02-01 20:45:35 |
言語 | F# (F# 4.0) |
結果 |
AC
|
実行時間 | 119 ms / 5,000 ms |
コード長 | 4,377 bytes |
コンパイル時間 | 10,523 ms |
コンパイル使用メモリ | 205,320 KB |
実行使用メモリ | 52,304 KB |
最終ジャッジ日時 | 2024-09-18 20:17:23 |
合計ジャッジ時間 | 11,473 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 119 ms
52,224 KB |
testcase_01 | AC | 119 ms
52,304 KB |
testcase_02 | AC | 119 ms
52,096 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.fsproj を復元しました (280 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/
ソースコード
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 = read int let ass = Array.zeroCreate (n + 1) for i in 0 .. n do let a = read int |> ModInt.init ass.[i] <- a let bs = Array.zeroCreate (n + 1) for i in 0 .. n do let a = read int |> ModInt.init bs.[i] <- a let cum = bs |> Array.scan (+) ModInt.zero let mutable ans = ModInt.zero for i in 0 .. n do let a = ass.[i] let b = cum.[n + 1 - i] ans <- ans + a * b ans |> ModInt.value |> puts () main() writer.Close()