3

この問題では、各行と列に少なくとも 1 つのコインがあるように、R コインを N*M グリッドに配置する方法の数を見つける必要があります。与えられた制約は、 N 、 M < 200 、 R < N*M です。最初はバックトラックを考えていたのですが、時間内に終わらないことに気づきました。誰かが私を別の解決策に導くことができますか? (DP 、閉じた形式の式。) 任意のポインターが適しています。ありがとう。

4

2 に答える 2

1

答え

OEIS シーケンス A055602によると、これに対する 1 つの可能な解決策は次のとおりです。

Let a(m, n, r) = Sum_{i=0..m} (-1)^i*binomial(m, i)*binomial((m-i)*n, r)

Answer = Sum_{i=0..N} (-1)^i*binomial(N, i)*a(M, N-i, R)

a に対して N+1 個の異なる値を評価する必要があります。

事前に計算された二項係数があると仮定すると、a の各評価は O(M) なので、合計の複雑さは O(NM) です。

解釈

この式は、包含排除原理を 2 回使用して導き出すことができます。

a(m,n,r) は、サイズ m*n のグリッドに r 個のコインを置き、m 列のすべてが占有されるようにする方法の数ですが、必ずしもすべての行が占有されるわけではありません。

包含-除外は、これを正しい答えに変えます。(アイデアは、a(M,N,R) から最初の見積もりを取得することです。すべての行が占有されているわけではないため、これは正しい答えを過大評価しているため、N のみを占有するケース a(M,N-1,R) を減算します。 -1 行。これは過小評価であるため、再度修正する必要があります...)

同様に、b(m,n,r) を考慮することで a(m,n,r) を計算できます。これは、行または列が占有されているかどうかを気にしないグリッドに r 個のコインを配置する方法の数です。これは、グリッド サイズ m*n で r 個の場所を選択する方法の数、つまり binomial(m*n,r) から簡単に導き出すことができます。IE を使用して、これを関数 a(m,n,r) に変換します。ここでは、すべての列が占有されていることがわかっています。

各正方形のコインの数に異なる条件を許可したい場合は、b(m,n,r) を適切なカウント関数に変更するだけです。

于 2012-07-24T18:31:23.020 に答える
0

これは難しいですが、各行と列に少なくとも 1 枚のコインを配置できる方法がいくつあるかを調べることから始めます (それらをリザーブ コインと呼びます)。答えは #1 の積になります(n! / r! (n - r)!) *。ここで、#2n = N*M - NUMBER_OF_RESERVE_COINSと #3r = (R - NUMBER_OF_RESERVE_COINS)は #4 の各行/列に 1 つのコインを予約する配置です。

＃4は、よりトリッキーなことが行われる場所です。N!=M の N*M の場合abs(N-M)、単一の行/列にあるリザーブ コインの数がわかります。主に時間がないため、次のステップに進む正しい方法を特定するのに苦労していますが (週末にはこれに戻ることができます)、有益な情報を提供できたことを願っています。あなたがプロセスを完了することができると言ったのは正しいです。

于 2012-07-24T17:59:33.763 に答える