n個のボールをm個の箱に入れよう
この記事はCompetitive Programming Advent Calendar Div2013の 14 日目の記事です。
初めまして。kuno4nです。
社会人から競技プログラミングを始めたへっぽこです。
さて、競技プログラマの皆様であれば、日常的にn個のボールをm個の箱に入れているかと思います。
ただ、場合の数を数えるとき、
・ボールは区別がつくか？
・箱は区別がつくか？
・１つの箱に２個以上入れていいのか？
・空の箱があっていいのか？
といったことが悩みの種かと思います。
まとめると、次の12通りに場合分けされます。
| ボール | 箱 | 最低1個入れる | 高々1個入れる | 入れ方に制限なし |
|---|---|---|---|---|
| 区別がつく | 区別がつく | count1 | count2 | count3 |
| 区別がつく | 区別がつかない | count4 | count5 | count6 |
| 区別がつかない | 区別がつく | count7 | count8 | count9 |
| 区別がつかない | 区別がつかない | count10 | count11 | count12 |
これらは写像12相と呼ばれております。
それぞれの場合の数を計算してみましょう。
dpのトレーニングになるだけでなく、包除原理、分割数、第二種スターリング数、ベル数といった概念の勉強にもなります。
前提事項
1≦n≦1000, 1≦m≦1000 程度を想定しています。
答えは1,000,000,007などのMODでとります。
配列Cには、パスカルの三角形等で組み合わせ数が事前に格納されているものとします。
const int MOD = 1000000007; long long C[1010][1010]; void make_C(){ memset(C, 0, (int)sizeof(C)); for(int i = 0; i < 1010; i++){ C[i][0] = C[i][i] = 1; for(int j = 1; j < i; j++) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; } }
count1: ◆ボール:区別有 ◆箱:区別有 ◆それぞれの箱に最低1個入れる
n個の区別できるボールを、m個の区別できる箱に、最低1個ずつ入れる場合の数をS(n, m)と書くと、
S(n, m) = S(n-1, m) * m + S(n-1, m-1) * m
という漸化式が成り立つので、dpで解けます。
この式の意味は、既にn-1番までのボールを入れ終わったと考えて、
- n-1番までのボールがm個の箱に最低1個ずつ入っている状態で、n番のボールを入れる場合。m個の箱それぞれに入れる場合がある。
- n-1番までのボールがm-1個の箱に最低1個ずつ入っている状態で、n番のボールを空の箱に入れる場合。空の箱はm通りの可能性がある。
という意味です。
long long dp[1010][1010]; // S(n, m) = S(n-1, m) * m + S(n-1, m-1) * m int count1_1(int n, int m){ if(n < m) return 0; memset(dp, 0, (int)sizeof(dp)); dp[0][0] = 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ // i-1個のボールがj個の箱に入っている状態で、i個目のボールを入れる場合 dp[i][j] += dp[i-1][j] * j; // i-1個のボールがj-1個の箱に入っている状態で、i個目のボールは新しい箱に入れる場合 dp[i][j] += dp[i-1][j-1] * j; dp[i][j] %= MOD; } } return dp[n][m]; }
また、包除原理を使っても解けます。
【m個以下の箱に入れる場合】-【m-1個以下の箱に入れる場合】+【m-2個以下の箱に入れる場合】-【m-3個以下の箱に入れる場合】……
を計算します。
int count1_2(int n, int m){ if(n < m) return 0; long long res = 0; for(int i = 1; i <= m; i++){ // i個以下の箱にn個のボールを入れる場合の数 long long tmp = (C[m][i] * modPow(i, n)) % MOD; // 包除原理 if((m-i)&1) res = (res - tmp + MOD) % MOD; else res = (res + tmp) % MOD; } return res; }
count2: ◆ボール:区別有 ◆箱:区別有 ◆それぞれの箱に高々1個入れる
n > mなら0、そうでなければmPnを計算。
// mPn int count2(int n, int m){ if(n > m) return 0; long long res = 1; while(n--) res = (res * m--) % MOD; return res; }
count3: ◆ボール:区別有 ◆箱:区別有 ◆入れ方に制限なし
m^nです。
// x^y (最小二乗法) int modPow(long long x, long long y){ long long r = 1, a = x % MOD; while(y > 0){ if((y&1) == 1) r = (r*a) % MOD; a = (a*a) % MOD; y /= 2; } return r; } int count3(int n, int m){ return modPow(m, n); }
count4: ◆ボール:区別有 ◆箱:区別無 ◆それぞれの箱に最低1個入れる
S(n, m) = S(n-1, m) * m + S(n-1, m-1)
という漸化式が成り立ち、これは第二種スターリング数と呼ばれます。
既にn-1番までのボールを入れ終わったと考えて、
- n-1番までのボールがm個の箱に最低1個ずつ入っている状態で、n番のボールを入れる場合。この場合は、m通り見分けがつく。
- n-1番までのボールがm-1個の箱に最低1個ずつ入っている状態で、n番のボールを空の箱に入れる場合。この場合は見分けがつかない。
という意味です。
long long dp[1010][1010]; // S(n, m) = S(n-1, m) * m + S(n-1, m-1) int count4_1(int n, int m){ if(n < m) return 0; memset(dp, 0, (int)sizeof(dp)); dp[0][0] = 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ // i-1個のボールがj個の箱に入っている状態で、i個目のボールを入れる場合。この場合はj通り区別できる。 dp[i][j] += dp[i-1][j] * j; // i-1個のボールがj-1個の箱に入っている状態で、i個目のボールは新しい箱に入れる場合。この場合は区別できない。 dp[i][j] += dp[i-1][j-1]; dp[i][j] %= MOD; } } return dp[n][m]; }
また、count1が計算できているのであれば、それをm!で割れば良いので、MOD上の逆元を使って解くことも出来ます。
MOD上の逆元については蟻本を参照して下さい。
// xのMOD上での逆元（MODが素数の場合） int modInverse(long long x){ return modPow(x, MOD-2); } int modDivision(long long p, long long q){ return ((p%MOD) * modInverse(q)) % MOD; } // n! int modFact(int n){ long long res = 1; while(n > 1) res = (res * n--) % MOD; return res; } int count4_2(int n, int m){ if(n < m) return 0; return modDivision(count1_1(n, m), modFact(m)); }
count5: ◆ボール:区別有 ◆箱:区別無 ◆それぞれの箱に高々1個入れる
n≦m なら問答無用で1通りです。
int count5(int n, int m){ if(n > m) return 0; return 1; }
count6: ◆ボール:区別有 ◆箱:区別無 ◆入れ方に制限なし
count4_1 と同様のdpを前もって実施しておけば、あとは「箱が1個の場合」「箱が2個の場合」……「箱がm個の場合」を足せばよいでしょう。
long long dp[1010][1010]; int count6(int n, int m){ // count4_1 と同様のdpを前もって実施 memset(dp, 0, (int)sizeof(dp)); dp[0][0] = 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ dp[i][j] += dp[i-1][j] * j; dp[i][j] += dp[i-1][j-1]; dp[i][j] %= MOD; } } // count4_1における「箱が1個の場合」「箱が2個の場合」……「箱がm個の場合」を足す long long res = 0; for(int i = 1; i <= m; i++) res = (res + dp[n][i]) % MOD; return res; }
count6: ◆ボール:区別有 ◆箱:区別無 ◆入れ方に制限なし
で、特にn=mのとき、ベル数と呼ばれます。
ベル数は、「n個の区別できるものを、空でないいくつかのまとまりに分ける場合の数」です。
B(n+1) = Σ(C[n][k]*B(k))
と表すことができ、この意味は例えばB(9)を計算するときは、
「1～8番のボールのうち、9番と一緒にしないボールをk個選ぶ。このk個のバラけ方はB(k)」
であり、kを0～8ととして足せば良い、という意味です。
// ベル数 long long dp_bell[1010]; int bellNumber(int n){ memset(dp_bell, 0, (int)sizeof(dp_bell)); dp_bell[0] = 1; for(int i = 1; i <= n; i++){ for(int j = 0; j <= i-1; j++){ dp_bell[i] = (dp_bell[i] + (C[i-1][j] * dp_bell[j])) % MOD; } } return dp_bell[n]; }
count7: ◆ボール:区別無 ◆箱:区別有 ◆それぞれの箱に最低1個入れる
n個のボールを横に並べて、n-1個の隙間にm-1個の仕切りを入れれば良いので、n-1個からm-1個を選ぶ組み合わせです。
int count7(int n, int m){ if(n < m) return 0; return C[n-1][m-1]; // 包除原理でもできるはずです }
count8: ◆ボール:区別無 ◆箱:区別有 ◆それぞれの箱に高々1個入れる
n≦mであれば、ただm個からn個を選ぶだけです。
int count8(int n, int m){ if(n > m) return 0; return C[m][n]; }
count9: ◆ボール:区別無 ◆箱:区別有 ◆入れ方に制限なし
みんなだいすき重複組合せです。
// nHm int count9_1(int n, int m){ // 範囲外アクセスに注意して下さい return C[n+m-1][m-1]; }
また、計算量がO((n^2)*m)となってしまいますが、dpでも解けます。
dp[i][j]を計算する際に、「j番目の箱に何個入れるか？」を考えます。
long long dp[1010][1010]; int count9_2(int n, int m){ memset(dp, 0, (int)sizeof(dp)); dp[0][0] = 1; // O((n^2)*m) です for(int i = 0; i <= n; i++){ for(int j = 1; j <= m; j++){ for(int k = 0; k <= i; k++){ // j番目の箱にはk個入れる。合計i個になるように。 dp[i][j] = (dp[i][j] + dp[i-k][j-1]) % MOD; } } } return dp[n][m]; }
count10: ◆ボール:区別無 ◆箱:区別無 ◆それぞれの箱に最低1個入れる
ボール1個の箱が少なくとも1つある場合と、どの箱も2個以上の場合に分けて、足します。
long long dp[1010][1010]; int count10(int n, int m){ if(n < m) return 0; memset(dp, 0, (int)sizeof(dp)); dp[0][0] = 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ // ボール1個の箱が少なくとも1つある場合。 // 1個箱に入れて、残りi-1個をj-1個の箱に分ける。 dp[i][j] += dp[i-1][j-1]; // ボール1個の箱が無い場合。 // まず1個づつ、j個の箱に入れてしまう。残りi-j個をj個の箱に分ける。 if(i >= j) dp[i][j] += dp[i-j][j]; dp[i][j] %= MOD; } } return dp[n][m]; }
count11: ◆ボール:区別無 ◆箱:区別無 ◆それぞれの箱に高々1個入れる
count5と同じく、n≦m なら問答無用で1通りです。
int count11(int n, int m){ if(n > m) return 0; return 1; }
count12: ◆ボール:区別無 ◆箱:区別無 ◆入れ方に制限なし
蟻本の「分割数」の項の問題です。n = mのとき、特にnの分割数といいます。
まずcount10と同様のdpを行っておき、1～mのsumを取れば答えです。
long long dp[1010][1010]; int count12_1(int n, int m){ // まずcount10と同様のdp memset(dp, 0, (int)sizeof(dp)); dp[0][0] = 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ dp[i][j] += dp[i-1][j-1]; if(i >= j) dp[i][j] += dp[i-j][j]; dp[i][j] %= MOD; } } // 1～mのsumをとる long long res = 0; for(int i = 1; i <= m; i++) res = (res + dp[n][i]) % MOD; return res; }
蟻本では、j-1個以下の箱に入れる場合の数と、必ずj個使う場合（最初に一個づつ入れてしまう）場合の数を足しています。
long long dp[1010][1010]; int count12_2(int n, int m){ memset(dp, 0, (int)sizeof(dp)); dp[0][0] = 1; for(int i = 0; i <= n; i++){ for(int j = 1; j <= m; j++){ // j-1個以下の箱に入れる場合 dp[i][j] += dp[i][j-1]; // 必ずj個使う場合（最初に一個づつ入れてしまう） if(i >= j) dp[i][j] += dp[i-j][j]; dp[i][j] %= MOD; } } return dp[n][m]; }
おまけ
せっかくボールを箱に入れてきたので、
「1～nの番号がついたボールを、1～nの番号がついた箱に、番号が異なるように入れる入れ方」を考えてみましょう。
下記は一例ですが、他にも包除原理などでも解けるはずです。
long long dp[1000010]; int count_omake(int n){ memset(dp, 0, (int)sizeof(dp)); dp[1] = 0; dp[2] = 1; for(int i = 3; i <= n; i++){ // まず、i番のボールを1～i-1のどれかの箱に入れる // （これでi-1通り）（k番の箱に入れたとする） // dp[i-2] は、k番のボールをi番の箱に入れた時。 // dp[i-1] は、k番のボールをi番の箱に入れない時。 // このとき、1～i-1番のボール全て、入れられない箱が1個あるわけだから、結局dp[i-1]となる。 dp[i] = ((i-1) * ((dp[i-2] + dp[i-1]) % MOD)) % MOD; } return dp[n]; }
