mod付きの二項係数を使ってみる - ロアちゃんかわいい

おはようございます。今日も夢月ロアちゃんが可愛いです。

この間のmod二項係数、折角実装したことだし使ってみるかと思い、問題を二問解いてみました。

C++なのにmain関数が数行で済んでしまった、暴力なのだ……なのだで思い出したんですが、夢月ロアちゃんというVtuberが天使のように天使です。友人諸氏はこんな駄文読んでないで早く動画を見に行ってください。

ロアちゃんの動画を見るのに忙しくてこんなブログ書いてる場合じゃないんですが、記録は大事なので仕方なく実装しておきます。

long long mod_pow(long long a, long long b, long long mod){
    if(b == 0) return 1;
    if(b % 2 == 0){
        long long d = mod_pow(a,b/2,mod);
        return (d*d)%mod;
    }else return a%mod*mod_pow(a,b-1,mod)%mod;
}
long long mod_combination(long long n,long long r,long long mod){
    if(r > n) return 0;
    if(n == r || r == 0) return 1;
    long long fact1 = 1,fact2 = 1;
    for(long long i = n; i >= n-r+1; i--) fact1 = fact1*i%mod;
    for(long long i = r; i >= 1; i--) fact2 = fact2*i%mod;
    return fact1*mod_pow(fact2,mod-2,mod)%mod;
}

まずは経路。高校数学で何度見たかって感じですね。
進む手順は(W-1)個の右向きの矢印と(H-1)個の上向きの矢印で表されるので、これらの並び替えの総数で表現可能。
よって、(H+W-2)!/{(H-1)!(W-1)!} = (H+W-2)C(H-1)で計算すればよい。

int main(){
    long long W,H; cin >> W >> H;
    cout << mod_combination(W+H-2,H-1,1e9+7);
}

関数貼るだけで終わるの、暴力だな？
便利なデータ構造とかは予め実装しておくことにしよう。

次は何とかかんとかいう問題。
かかる操作の回数が最小→連続している青いボールは一度に回収される。
なので赤の隙間（両端を含むのでN-K+1個隙間がある）からi個選んで、各場合について、各隙間最低青ボールが一個は入るような並べ方の総数を考えればOK。
赤の隙間を選ぶのは(N-K+1)Ci通り
青ボールの詰め方は｜（仕切り、ここでは赤ボール）と◯（青ボール）の並び替えを考えればよくて、最小でも各隙間に一個は入らないと行けない。
◯の数はK個、｜の数はi-1個なので、◯の隙間に｜を入れればよいので(K-1)C(i-1)通り。
結局(N-K+1)Ci×(K-1)C(i-1)通りを1e9+7で割った余りを求めればよい。
なので後は暴力をします。

int main(){
    const long long mod = 1e9+7;
    long long n,k; cin >> n >> k;
    for(long long i = 1; i <= k; i++) cout << mod_combination(n-k+1,i,mod)*mod_combination(k-1,i-1,mod)%(mod) << endl;
}

ロアちゃんかわいいって感じですね。どうでもいいけど学生証見つかりました。

ではおやすみなさい。