Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

包除原理を応用する問題

https://onlinejudge.u-aizu.ac.jp/problems/DPL_5_C

問題

n個の区別できるボールをk個の区別できる箱に入れるとき、可能な入れ方の総数を求めてください。ただし、どの箱にも、1つ以上のボールを入れる。

考え方

ベースとなる考え方は、

  1. とにかくそれぞれのボールに1からkの数字をつけてみる (kn)
  2. この場合、空箱を含んでしまうから、空箱を含んでる場合を除く

です。ここで2を求めるのが仕事ということなります。

解法1: DP

n個のボールをk-i個の箱で消費する小さな問題を解いて、それを大きな問題で使うことが出来ます。

fn solve() {
    input! {
        N: usize, K: usize,
    }
    let p = 1_000_000_007;
    let modcomb = ModComb::new(K+1, p);

    let mut dp = vec![0; K+1];
    dp[1] = 1;
    for i in 2..K+1 { // 埋める箱の数
        dp[i] = modpow(i, N, p);
        for j in 1..i { // j: 空箱の数
            let sub = modcomb.nCk(i, j) * dp[i-j];
            let sub = sub % p;
            dp[i] = (dp[i] + p - sub) % p;
        }
    }
    // dbg!(&dp);
    println!("{}", dp[K] % p);
}

解法2: 包除定理

包除原理の意味と証明|思考力を鍛える数学

包除定理において、A(i)を「i番目の箱が空である」という事象とします。すると、左辺がまさに求めるものということになります。次に右辺において、Sum(|A(i)|)というのは、C(k,1) (k-1)nに等しいです。同様に、Sum(|A(i) かつ A(j)|)というのは、C(k,2) (k-2)nに等しいです。

一言でいうと、奇数個のintersectionは足し。偶数個のintersectionは引きを実装します。

    input! {
        n: u64, k: u64
    }
    let p = 1_000_000_007;
    let mc = ModComb::new(1000,p);
    let res = modpow(k,n,p);
    let mut cnt = 0;
    for m in 1..k {
        let tmp = (mc.nCk(k, m) * modpow(k-m, n, p)) % p;
        if m % 2 == 1 {
            cnt = cnt + tmp;
        } else {
            cnt = (cnt + p - tmp) % p;
        }
    }
    let res = (res + p - cnt) % p;
    println!("{}", res);

考察

スターリング数というのと関係ありそうなのですが、わからなかったです。