積の和典型 - ei1333の日記

これだされるの60回目なのになんで解けないんあ　記憶喪失

積の和

次の問題を考える。

長さ ${N}$ で総和が ${M}$ の任意の整数列 ${a}$ について $\prod_{i=1}^{N} a_i$ を求め、その総和を ${10^9+7}$ で割った余りで求めよ。

多くの場合、ありうる集合全てに対してそのまま積を求める愚直解は間に合わない場合が多い。従って、別の解法が求められる。

式をよく見ると $a_i = ( \underbrace{ 1 + 1 + \cdots + 1 }_{ a_i } )$ なので、 $\prod_{i=1}^{N} a_i$ は各 ${i(1 \leq i \leq N)}$ について ${a_i}$ 個の ${1}$ から ${1}$ 個選ぶ方法の個数と一致する。

この事実を踏まえて、箱とボールで言い換えみる。区別できる ${N}$ 個の箱があって箱 ${i}$ には区別できる ${a_i}$ 個のボールが入っている。このとき、それぞれの箱についてその中のボール ${1}$ 個を選んで黒く塗る方法の個数に一致することがわかる。

したがって、ありうる全ての集合を考える場合は、それぞれの箱に黒いボールがちょうど ${1}$ つ入った分け方を考えれば良い。

これは区別できない ${M}$ 個のボールを区別できる ${N}$ グループに分けた上で、それぞれのグループのボール ${1}$ 個を選んで(グループの中ではボールは区別可能)黒く塗る方法の個数に等しく、 $\binom {M+N-1} {N+N-1}$ のような単純な二項係数で表せることがわかる( ${M}$ 個のボールに ${N-1}$ 個の仕切りを追加して ${N+N-1}$ 個選ぶ。選んだ要素を{黒,仕切り,黒,仕切り,...} に置き換えると実際に示した分け方に対応している)。

実際に積を求めて足さなくても答えが求まることが重要で、この言い換えによって解ける問題が多く出題されている。ここからは、このテクで解ける問題とその解法を説明する。

ARC110 D - Binomial Coefficient is Fun (600点)

atcoder.jp

問題概要

長さ ${N}$ の数列 ${A}$ が与えられる。

長さ ${N}$ で総和が ${M}$ 以下の任意の整数列について $\prod_{i=1}^{N} \binom {A_i} {B_i}$ を求め、その総和を ${10^9+7}$ で割った余りで求めよ。

解法

${x_i}$ 個の ${1}$ から ${1}$ 個選ぶところを ${A_i}$ 個選べると思えば良い。

${S=\sum_{i=1}^{N} A_i}$ とする。区別できない ${M}$ 個以下のボールを区別できる ${N}$ グループに分けた上で、それぞれのグループのボールから ${A_i}$ 個選んで(グループの中ではボールは区別可能)黒く塗る方法の個数に等しく、 $\binom {M+N} {S+N}$ である( ${M}$ 個のボールに ${N}$ 個の仕切りを追加して ${S+N}$ 個選ぶ。選んだ要素を{黒 ${\times A_1}$ ,仕切り,黒 ${\times A_2}$ ,仕切り,...,黒 ${\times A_N}$ ,仕切り} に置き換えると実際に示した分け方に対応している, 最後の仕切り以降の要素は "以下" を表現している)。

（これ裏話なんですが、以下が見えてなくて1日考えてしまった　バカ）

（一番最初の問題として書いておいてアレなんですが、これは積の和ではないという指摘が出ています）

atcoder.jp

問題概要

区別できる ${N}$ 人に対して ${K}$ 回クッキーを渡す。

${i(1 \leq i \leq K)}$ 日目には ${a_i}$ 人選んでそれぞれに ${1}$ 枚ずつクッキーを渡す。

考えられる全ての配り方について、 ${K}$ 日間で人 ${i(1 \leq i \leq N)}$ が受け取ったクッキの枚数を ${c_i}$ として $\prod_{i=1}^{N} c_i$ を求めて、その和を ${10^9 + 7}$ で割った余りで求めよ。

解法

$\prod_{i=1}^{N} c_i$ は、それぞれの人が持っているクッキーから ${1}$ 枚ずつ選ぶ方法の個数と等しい。

このときに選んだクッキーを黒、選ばなかったクッキーを白に塗ることにする。

すると次の条件を満たすクッキーの配り方の方法と等しいことが分かる。

${i(1 \leq i \leq K)}$ 日目に黒と白クッキーを合わせて ${a_i}$ 人に ${1}$ 枚ずつ渡す
それぞれの人に対して黒クッキーを1枚ずつ渡す

${i}$ 日目までクッキーを渡したときに、黒クッキーを既に渡した人数が ${j}$ となる方法の個数を状態としたDPにより求められることが分かる。自然な実装をすると、状態数 ${O(KN)}$ 遷移 ${O(N)}$ となり ${O(N^2 K)}$ で間に合うため、おわり。

ARC124 E - Pass to Next (800点)

atcoder.jp

問題概要

${N}$ 人が円環状に並んでいる。人 ${i}$ は ${a_i}$ 個のボールを持っている。

それぞれの人が持っているボールのうちいくつかを同時に右隣の人に渡すことによってできる全ての数列の集合を ${S}$ とする。

$\sum_{x \in S} \prod_{i=1}^{N} x_i$ を ${\bmod 998244353}$ で割った余りで求めよ。

解法

以下の説明では、 ${a_i}$ 個のボールが箱 ${i}$ に入っていて、そのボールを人 ${i}$ または ${i+1}$ に渡すことを考えている。

$\prod_{i=1}^{N} x_i$ は、それぞれの人が持っているボールから ${1}$ 個ずつ選ぶ方法の個数と等しい。

このときに選んだボールを黒に塗ることにする。

すると次の条件を満たすボールの配り方の方法と等しいことが分かる。

箱 ${i}$ または箱 ${i+1}$ のいずれかに人 ${i}$ に対応する黒いボールが存在する
箱 ${i}$ の ${a_i}$ 個のボールは人 ${i}$ または人 ${i+1}$ のいずれかに配られる
人 ${i}$ のみに配られる箱 ${i}$ が一つ以上存在する (= 一人以上右隣の人にボールを渡さない = 考察をすると、一人以上右隣の人にボールを渡さないことを仮定した上で解くと答えに一致することが分かる。全員が右隣の人にボールを渡す場合は、ボールを渡す個数を ${1}$ 個ずつ減らしても同じ数列になっている)

黒いボールは一つの箱に ${0}$ 個以上 ${2}$ 個以下含まれることが分かる。今、 ${i}$ 番目の箱の配り方を考えていることにする。すると、以下の4通りに場合分けできる。

黒 ${0}$ 個のパターン : 人 ${i-1}$ の黒ボールが箱 ${i-1}$ にあって、人 ${i}$ の黒ボールが ${i+1}$ にある
単にボールを人 ${i,i+1}$ に配る方法の個数。つまり ${a_i + 1}$ 通り。
黒 ${1}$ 個のパターン1 : 人 ${i-1}$ の黒ボールが箱 ${i}$ にあって、人 ${i}$ の黒ボールが ${i+1}$ にある
ボールを ${i,i+1}$ に配るが、 ${i+1}$ に配られたボールのうち ${1}$ つは黒く塗られている。つまり $\binom{ a_i + 1 }{ 2 }$ 通り(2つ選んで1つは仕切りで1つを黒く塗る）。
黒 ${1}$ 個のパターン2 : 人 ${i-1}$ の黒ボールが箱 ${i-1}$ にあって、人 ${i}$ の黒ボールが ${i}$ にある
上と同様で $\binom{ a_i + 1 }{ 2 }$ 通り。
黒 ${2}$ 個のパターン : 人 ${i-1}$ の黒ボールが箱 ${i}$ にあって、人 ${i}$ の黒ボールが ${i}$ にある
ボールを ${i,i+1}$ にくばるが、 ${i,i+1}$ に配られたボールのうちそれぞれ ${1}$ つは黒く塗られている。つまり $\binom{ a_i + 1 }{ 3 }$ 通り(3つ選んで1つは仕切りで、仕切りの左側と右側のうち1つずつを黒く塗る）。

DP により求めることを考えると、状態に人 ${i}$ の黒ボールを箱 ${i}$ に入れたかどうか、人 ${i}$ のみに配られる箱 ${i}$ が一つ以上存在するかどうかをもたせれば十分。(1つ以上存在するかを考える場合、上の4通りは嘘で6通りくらいあるので適当に場合分けしてね) これを ${N}$ 回繰り返せばよいので、計算量は ${O(N)}$ 。