結果

問題 No.766 金魚すくい
ユーザー tottoripapertottoripaper
提出日時 2018-12-25 17:34:22
言語 OCaml
(5.1.0)
結果
WA  
実行時間 -
コード長 2,304 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 21,888 KB
実行使用メモリ 9,728 KB
最終ジャッジ日時 2024-10-09 00:33:03
合計ジャッジ時間 7,503 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 15 ms
6,656 KB
testcase_01 AC 14 ms
6,784 KB
testcase_02 AC 13 ms
6,784 KB
testcase_03 AC 14 ms
6,784 KB
testcase_04 AC 14 ms
6,784 KB
testcase_05 AC 13 ms
6,784 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 13 ms
6,820 KB
testcase_09 WA -
testcase_10 AC 13 ms
6,784 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 17 ms
7,424 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 266 ms
9,600 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 AC 71 ms
8,832 KB
testcase_36 AC 68 ms
8,704 KB
testcase_37 AC 275 ms
9,600 KB
testcase_38 AC 272 ms
9,600 KB
testcase_39 AC 264 ms
9,600 KB
testcase_40 AC 265 ms
9,472 KB
testcase_41 AC 267 ms
9,472 KB
testcase_42 AC 253 ms
9,600 KB
testcase_43 AC 13 ms
6,656 KB
testcase_44 AC 13 ms
6,784 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)
  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