ABC221 H - Count Multiset - かんプリンの学習記録

形式的冪級数を用いた解法です．

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${k=1,2,\cdots ,N}$ について以下の値を求めよ．

個の正整数から多重集合のうち，以下の2つの条件をすべて満たすものの個数
- 要素の総和が ${N}$
- 任意の正整数を高々 ${M}$ 個しか含まない

${1\leq M\leq N\leq 5000}$

解説

多重集合に各整数 ${i}$ がいくつ含まれるかを考えると
$f(x,y)=\prod_{i=1}^{\infty}\frac{1-(xy^i)^{M+1}}{1-xy^i}$ としたときの ${[x^ky^N]f}$ が答えとなる．

${\displaystyle \begin{align*} f(xy,y)&=\prod_{i=1}^{\infty}\frac{1-(xy^{i+1})^{M+1}}{1-xy^{i+1}}\\ &=\prod_{i=2}^{\infty}\frac{1-(xy^i)^{M+1}}{1-xy^i}\\ &=f(x,y)\times\frac{1-xy}{1-(xy)^{M+1}} \end{align*}}$

${\begin{align*}f(xy,y)(1-(xy)^{M+1})&=f(x,y)(1-xy)\\ [x^ky^N]f(xy,y)(1-(xy)^{M+1})&=[x^ky^N]f(x,y)(1-xy)\\ [(xy)^ky^{N-k}]f(xy,y)(1-(xy)^{M+1})&=[x^ky^N]f(x,y)(1-xy)\\ [x^ky^{N-k}]f(x,y)(1-x^{M+1})&=[x^ky^N]f(x,y)(1-xy)\\ [x^ky^{N-k}]f-[x^{k-M-1}y^{N-k}]f&=[x^ky^N]f-[x^{k-1}y^{N-1}]f\\ \end{align*}}$
となるので
${[x^ky^N]f=[x^{k-1}y^{N-1}]f+[x^ky^{N-k}]f-[x^{k-M-1}y^{N-k}]f}$
となり，DP遷移が分かる．
kanpurin.hatenablog.com

提出プログラム

https://atcoder.jp/contests/abc221/submissions/26574776

感想

考察がほぼ不要で解けた．形式的冪級数すごい．