AtCoder ABC 132 D - Blue and Red Balls (Kotlin) - あるエンジニアのAtCoder奮闘記

irisruneです。残念ながら今回のコンテストは不参加でした、問題を見るとD問題以降がかなり難しくなっているようですね。

問題

考察（+剰余周りの実装）面の問題ですが、ABCが新形式になって以降のD問題としてはかなり難しいと思います。ただしPythonなどを使う場合は実行時間に余裕があることが救いかもしれません（パスカルの三角形を使う場合は余裕がないようです）。

const val MOD = 1000000007

fun COMinit(m: Int): Pair<List<Long>, List<Long>> {
    val fac = mutableListOf(1L, 1L)
    val finv = mutableListOf(1L, 1L)
    val inv = mutableListOf(1L, 1L)
    for (i in 2 until m + 1) {
        fac.add((fac[i - 1] * i) % MOD)
        inv.add(MOD - ((inv[MOD % i] * (MOD / i)) % MOD))
        finv.add((finv[i - 1] * inv[i]) % MOD)
    }
    return Pair(fac, finv)
}

fun COM(m: Int, r: Int, fac: List<Long>, finv: List<Long>): Long {
    if (m < r) return 0L
    if (m < 0 || r < 0) return 0L
    return (fac[m] * ((finv[r] * finv[m - r]) % MOD)) % MOD
}

fun main(args: Array<String>){
    val (n, k) = readLine()!!.split(" ").map(String::toInt)
    val (fac, finv) = COMinit(Math.max(n - k + 1, k - 1))
    for (i in 1 until k + 1) {
        println((COM(n - k + 1, i, fac, finv) * COM(k - 1, i - 1, fac, finv)) % MOD)
    }
}

まず、剰余を考慮した二項係数の計算についてこちらのブログから拝借して実装したため紹介いたします。

drken1215.hatenablog.com

こちらのアルゴリズムを見た時に何かの機会に使うかもしれないと思っていましたがそれが今回でした。初めパスカルの三角形を用いて求めることを考えていたわけですが、~~差の剰余の求め方をど忘れしていたため断念しました（今思えば差がマイナスになる場合を考慮してアルゴリズムを組めばいいだけでした）。~~よく考えたらパスカルの三角形で差を求める機会はないですね…何を見ていたんでしょうか。

実装面は剰余を考慮した二項係数の計算ができるかが全てのため、残りは考察面の問題となります。

ここで白状しますと、自分がこの問題を解いた流れとしては、