結果
問題 | No.766 金魚すくい |
ユーザー |
![]() |
提出日時 | 2018-12-25 17:38:50 |
言語 | OCaml (5.2.1) |
結果 |
AC
|
実行時間 | 274 ms / 1,500 ms |
コード長 | 2,313 bytes |
コンパイル時間 | 385 ms |
コンパイル使用メモリ | 21,580 KB |
実行使用メモリ | 9,600 KB |
最終ジャッジ日時 | 2024-10-09 00:33:24 |
合計ジャッジ時間 | 7,008 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
let rec expt ( * ) e a n =if n = 0 theneelse if n land 1 = 1 thena * expt ( * ) e (a * a) (n / 2)elseexpt ( * ) e (a * a) (n / 2)let mod_expt a n mo = expt (fun x y -> x * y mod mo) 1 a nlet mod_inv a p = mod_expt a (p - 2) pmodule Combination : sigtype tval init : n:int -> modulo:int -> tval fact : int -> t -> intval inv_fact : int -> t -> intval nPk : int -> int -> t -> intval nCk : int -> int -> t -> intval nHk : int -> int -> t -> intend = structtype t = int * int array * int arraylet init ~n ~modulo =let f = Array.make (n + 1) 0 inlet () =f.(0) <- 1;for i = 1 to n dof.(i) <- f.(i - 1) * i mod modulodone inlet inv_f = Array.make (n + 1) 0 inlet () =inv_f.(n) <- mod_inv f.(n) modulo;for i = n - 1 downto 0 doinv_f.(i) <- inv_f.(i + 1) * (i + 1) mod modulodone in(modulo, f, inv_f)let fact n (_, f, _) = f.(n)let inv_fact n (_, _, inv_f) = inv_f.(n)let nPk n k ((mo, _, _) as c) =if n < k then0elsefact n c * inv_fact (n - k) c mod molet nCk n k ((mo, _, _) as c) =if n < k then0elsefact n c * inv_fact k c mod mo * inv_fact (n - k) c mod molet nHk n k c = if n = 0 && k = 0 then 1 else nCk (n + k - 1) k cendlet id x = xlet mo = 1_000_000_007let c = Combination.init ~n:200100 ~modulo:molet (n, m, p) = Scanf.scanf "%d %d %d" (fun n m p -> (n, m, p))let (p, q) = (p * mod_inv 100 mo mod mo, (100 - p) * mod_inv 100 mo mod mo)let v = Array.init n (fun _ -> Scanf.scanf " %d" id)let () =Array.sort (fun x y -> - compare x y) v;for i = 1 to n - 1 dov.(i) <- (v.(i) + v.(i - 1)) mod modonelet cnt = ref 0let () =for i = 1 to n - 1 do (* i 匹目まで掬うことができた *)let prob = Combination.nHk (i + 1) (m - 1) c mod mo * mod_expt p m mo mod mo * mod_expt q i mo mod mo incnt := (!cnt + v.(i - 1) * prob mod mo) mod modone;for j = 0 to m - 1 do (* N 匹目まで掬うことができた.破れたポイは j 個 *)let prob = Combination.nHk n j c mod mo * mod_expt p j mo mod mo * mod_expt q n mo mod mo incnt := (!cnt + v.(n - 1) * prob mod mo) mod modone;print_int !cnt;print_newline ()