結果

問題 No.766 金魚すくい
ユーザー tottoripaper
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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