結果
問題 | No.758 VVVVV |
ユーザー |
![]() |
提出日時 | 2018-12-25 15:55:48 |
言語 | OCaml (5.2.1) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 2,040 bytes |
コンパイル時間 | 217 ms |
コンパイル使用メモリ | 21,760 KB |
実行使用メモリ | 14,592 KB |
最終ジャッジ日時 | 2024-10-09 00:32:41 |
合計ジャッジ時間 | 2,361 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
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 n = Scanf.scanf "%d" idlet g = Array.make (n + 1) []let () =for i = 1 to n - 1 dolet (a, b) = Scanf.scanf " %d %d" (fun a b -> (a, b)) ing.(a) <- b :: g.(a);g.(b) <- a :: g.(b)donelet rec dfs v p =match g.(v) with[w] when w = p -> 1 (* v は葉 *)| _ -> List.fold_left (fun s w -> if w <> p then s + dfs w v else s) 0 g.(v)let m = dfs 1 (-1)let mo = 1_000_000_007let c = Combination.init ~n:200100 ~modulo:molet cnt = if n >= 3 thenCombination.nCk (n - 1) (m - 1) c * Combination.nCk (n - 2) (m - 1) c mod mo * mod_inv m mo mod moelse1let () =print_int cnt;print_newline ()