ABC 221 H - Count Multiset

• 問題
• AC

分割数っぽい数え上げなので分割数っぽいDPを考える。

まずは分割数のDPを思い出す。自然数$n$を$k$個の正整数の和に分割する場合の数を$P(n, k)$とする。分割の中に1を含まないものは$n-k$の$k$分割のすべての項を$1$増加させて得られ、分割の中に1を含むものは$n-1$の$k-1$分割に1を付加すれば得られるのだった。漸化式で表すと

$$P(n, k) = P(n-k, k) + P(n-1, k-1)$$

このDPを、同じ数を$M$個より多くは含まないという制約（以下、単に制約と呼ぶ）に合うように修正することを考える。制約付きの分割の総数を$P'(n, k)$とする。

上の遷移の一つ目の項、つまり分割の中に1を含まないものを$n-k$の$k$分割のすべての項を$1$増加させて得る場合については、制約はそのまま守られるのでこのままでよさそう。一方、二つ目の項、つまり、分割の中に1を含むものを数えたい場合、このままだと1を$M+1$個含むものも数えてしまうことになるので、これを除きたい。

$n$の$k$分割で$1$をちょうど$M+1$個含み、他は制約を満たしているようなものの総数 = $n-(M+1)$の$k-(M+1)$分割で1を含まず、かつ制約を満たしているようなものの総数 = $n-(M+1)- (k-(M+1))$、つまり$n-k$の$k-(M+1)$分割で、制約を満たしているようなものの総数

と言い換えると、最後の量は$P'(n-k, k-(M+1))$に等しいので、漸化式は

$$P'(n, k) = P'(n-k, k) + P'(n-1, k-1) - P'(n-k, k-(M+1))$$

となる。

---

スターリング数っぽい数え上げがスターリング数っぽいDPでできる、はけっこう見るけど、分割数っぽい数え上げではうまくいく問題を見た記憶がなくて、遷移を考え始めるまでに時間がかかった……が、例えばJOI 2009 予選 F - ビンゴ がそうだったのを思い出した。