094 D - Blue and Red Balls

解説

数学的な組み合わせ処理とmodつきnCrの実装だけです. 後者は自分用のライブラリ・関数を用意しておくべきです.

入出力

1
2
let N,K = stdin.ReadLine().Split() |> Array.map int64 |> (fun x -> x.[0],x.[1])
solve N K |> Array.iter stdout.WriteLine

順列・組み合わせ系の関数

modつきの計算の場合, いくつかの処理が簡略化できます. 逆数を取る走査もかけ算で表せるためそれを前提にした実装です. 単純に順列はp, 組み合わせはcにしています.

1
2
3
4
5
  let MOD = 1_000_000_007L
  let p n r = let rec frec acc n r = if r=0L then acc else frec ((n*acc)%MOD) (n-1L) (r-1L) in frec 1L n r
  let rec powm x n = if n=0L then 1L else if n%2L=0L then powm (x*x % MOD) (n/2L) else (x * (powm x (n-1L)) % MOD)
  let inv a = powm a (MOD-2L)
  let c n r = ((p n r) * (inv (p r r))) % MOD

これ以外の順列・組み合わせ系の関数実装サンプルがArithmetics.fsxにあります. 必要に応じて参照してください.

各iに対する計算

1
  [|1L..K|] |> Array.map (fun i -> c (N-K+1L) i * c (K-1L) (i-1L) % MOD)

まとめ

1
2
3
4
5
6
7
8
9
let solve N K =
  let MOD = 1_000_000_007L
  let p n r = let rec frec acc n r = if r=0L then acc else frec ((n*acc)%MOD) (n-1L) (r-1L) in frec 1L n r
  let rec powm x n = if n=0L then 1L else if n%2L=0L then powm (x*x % MOD) (n/2L) else (x * (powm x (n-1L)) % MOD)
  let inv a = powm a (MOD-2L)
  let c n r = ((p n r) * (inv (p r r))) % MOD
  [|1L..K|] |> Array.map (fun i -> c (N-K+1L) i * c (K-1L) (i-1L) % MOD)
let N,K = stdin.ReadLine().Split() |> Array.map int64 |> (fun x -> x.[0],x.[1])
solve N K |> Array.iter stdout.WriteLine