結果

問題 No.766 金魚すくい
ユーザー tottoripapertottoripaper
提出日時 2018-12-25 17:38:50
言語 OCaml
(5.1.0)
結果
AC  
実行時間 276 ms / 1,500 ms
コード長 2,313 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 21,760 KB
実行使用メモリ 9,728 KB
最終ジャッジ日時 2024-04-17 08:45:23
合計ジャッジ時間 6,582 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 13 ms
6,816 KB
testcase_01 AC 13 ms
6,940 KB
testcase_02 AC 13 ms
6,944 KB
testcase_03 AC 13 ms
6,940 KB
testcase_04 AC 13 ms
6,944 KB
testcase_05 AC 13 ms
6,940 KB
testcase_06 AC 13 ms
6,940 KB
testcase_07 AC 13 ms
6,940 KB
testcase_08 AC 13 ms
6,940 KB
testcase_09 AC 13 ms
6,940 KB
testcase_10 AC 13 ms
6,940 KB
testcase_11 AC 13 ms
6,944 KB
testcase_12 AC 13 ms
6,940 KB
testcase_13 AC 16 ms
7,424 KB
testcase_14 AC 17 ms
7,552 KB
testcase_15 AC 16 ms
7,424 KB
testcase_16 AC 16 ms
7,296 KB
testcase_17 AC 17 ms
7,552 KB
testcase_18 AC 15 ms
7,296 KB
testcase_19 AC 16 ms
7,552 KB
testcase_20 AC 16 ms
7,424 KB
testcase_21 AC 16 ms
7,424 KB
testcase_22 AC 17 ms
7,552 KB
testcase_23 AC 258 ms
9,600 KB
testcase_24 AC 265 ms
9,600 KB
testcase_25 AC 276 ms
9,600 KB
testcase_26 AC 257 ms
9,600 KB
testcase_27 AC 274 ms
9,728 KB
testcase_28 AC 261 ms
9,600 KB
testcase_29 AC 260 ms
9,600 KB
testcase_30 AC 258 ms
9,600 KB
testcase_31 AC 274 ms
9,600 KB
testcase_32 AC 267 ms
9,600 KB
testcase_33 AC 126 ms
9,600 KB
testcase_34 AC 126 ms
9,600 KB
testcase_35 AC 70 ms
8,832 KB
testcase_36 AC 68 ms
8,832 KB
testcase_37 AC 274 ms
9,600 KB
testcase_38 AC 273 ms
9,600 KB
testcase_39 AC 264 ms
9,472 KB
testcase_40 AC 265 ms
9,600 KB
testcase_41 AC 269 ms
9,600 KB
testcase_42 AC 253 ms
9,600 KB
testcase_43 AC 13 ms
6,944 KB
testcase_44 AC 13 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

let rec expt ( * ) e a n =  
  if n = 0 then
    e
  else if n land 1 = 1 then
    a * expt ( * ) e (a * a) (n / 2)
  else
    expt ( * ) e (a * a) (n / 2)

let mod_expt a n mo = expt (fun x y -> x * y mod mo) 1 a n
let mod_inv a p = mod_expt a (p - 2) p

module Combination : sig
  type t
  val init : n:int -> modulo:int -> t
  val fact : int -> t -> int
  val inv_fact : int -> t -> int
  val nPk : int -> int -> t -> int
  val nCk : int -> int -> t -> int
  val nHk : int -> int -> t -> int
end = struct
  type t = int * int array * int array
  let init ~n ~modulo =
    let f = Array.make (n + 1) 0 in
    let () =
      f.(0) <- 1;
      for i = 1 to n do
        f.(i) <- f.(i - 1) * i mod modulo
      done in
    let inv_f = Array.make (n + 1) 0 in
    let () =
      inv_f.(n) <- mod_inv f.(n) modulo;
      for i = n - 1 downto 0 do
        inv_f.(i) <- inv_f.(i + 1) * (i + 1) mod modulo
      done 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 then
      0
    else
      fact n c * inv_fact (n - k) c mod mo
  let nCk n k ((mo, _, _) as c) =
    if n < k then
      0
    else
      fact n c * inv_fact k c mod mo * inv_fact (n - k) c mod mo
  let nHk n k c = if n = 0 && k = 0 then 1 else nCk (n + k - 1) k c                               
end

let id x = x

let mo = 1_000_000_007
let c = Combination.init ~n:200100 ~modulo:mo

let (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 do
    v.(i) <- (v.(i) + v.(i - 1)) mod mo
  done

let cnt = ref 0
let () =
  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 in
    cnt := (!cnt + v.(i - 1) * prob mod mo) mod mo
  done;
  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 in
    cnt := (!cnt + v.(n - 1) * prob mod mo) mod mo
  done;
  print_int !cnt;
  print_newline ()
0