# ABC221 H - Count Multiset
## 問題リンク
- https://atcoder.jp/contests/abc221/tasks/abc221_h

## 解法
形式的べき級数による解法をとります。

まず, 元の問題を以下のように解釈します.

> $M$ 以下の非負整数からなる数列 $x$ であって $\sum_{n=1}^{\infty}{nx_n}$ を満たすようなものはいくつあるか?

$x$の指数に選んだ要素の和を, $y$ の指数に要素の個数を乗せることで求めるべきは以下で表される $(k=1,2,\cdots,N)$

$$[x^Ny^k]\prod_{i=1}^{\infty}{\sum_{0\leq j\leq M}{x^{ij}y^j}}$$

Σ部分をきれいにして

$$[x^Ny^k]\prod_{i=1}^{\infty}{\frac{1-(x^iy)^{M+1}}{1-x^iy}}$$

となる. ここで, 分母の形に[見覚えがある](https://maspypy.com/%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%83%BB%E5%BD%A2%E5%BC%8F%E7%9A%84%E3%81%B9%E3%81%8D%E7%B4%9A%E6%95%B0-%E9%AB%98%E9%80%9F%E3%81%AB%E8%A8%88%E7%AE%97%E3%81%A7%E3%81%8D%E3%82%8B%E3%82%82%E3%81%AE#toc21)ということで同様のアプローチをしてみる.

$$f(x,y)=\frac{1-(xy)^{M+1}}{1-xy}$$
$$F(x,y)=\prod_{i=1}^{\infty}{f(x^i,y)}$$

とする. ここで, 任意の $n$ に対して以下が成り立つ
$$f(x^n,xy)=f(x^{n+1},y)$$
したがって, 以下のように変形していくことができる.
$$
\begin{aligned}
f(x,y)F(x,xy)&=f(x,y)\prod_{i=1}^{\infty}{f(x^i,xy)}\\&=f(x,y)\prod_{i=1}^{\infty}{f(x^{i+1},y)}\\&=\prod_{i=1}^{\infty}{f(x^{i},y)}\\&=F(x,y)
\end{aligned}
$$

すなわち

$$\left(1-(xy)^M\right)F(x,xy)=(1-xy)F(x,y)$$

が成り立つ.
$F(x,y)$ の $x^iy^j$ の係数を $a_{i,j}$とする. この時, 左辺は以下のようになる.

$$
\begin{aligned}
\left(1-(xy)^M\right)F(x,xy)
&=\left(1-(xy)^M\right)\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}{a_{ij}x^{i+j}y^j}\\
&=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}{(a_{i-j,j}-a_{i-j,j-M})x^iy^j}
\end{aligned}
$$

一行目の式変形に $F(x,y)$ が $xy$ を用いて表示できることを利用した.

また, 右辺も同様にやると以下のようになる

$$
\begin{aligned}
(1-xy)F(x,y)&=(1-xy)\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}{a_{ij}x^iy^j}\\
&=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}{(a_{i,j}-a_{i-1,j-1})x^iy^j}
\end{aligned}
$$

係数比較をすると以下が得られる

$$a_{i-j,j}-a_{i-j,j-M}=a_{i,j}-a_{i-1,j-1}$$

移項して

$$a_{i,j}=a_{i-j,j}-a_{i-j,j-M}+a_{i-1,j-1}$$

よって $O(N^2)$ のDPで $a$ を埋めることができる.

以上よりこの問題が解けた.