# 競プロキャンプ2023関西 L - (sum)mer

## 問題リンク
- https://mofecoder.com/contests/kyoprocamp2023west/tasks/kyoprocamp2023west_l

## 解法
### 立式
FPSをつかって立式します.指数に総和,係数に $A_i^2+A_i$ の総積を乗せることで以下のように答えを表せます.

> $f=\sum_{i=1}^{\infty}{(i^2+i)x^i}$ として$[x^M]f^N$

以下,この値を求めていきます.

### 変形
$f$ がなんだかわかりにくいので,変形するべくじっと形をにらんでみましょう... $i^2+i$ というのがよくわからないですね.
等式
$$i^2+i=2\binom{i+1}{2}$$
が成り立ちますから,それを用いて次のように $f$ を以下のように書きなおします.

$$
\begin{aligned}
f&=\sum_{i=1}^{\infty}{(i^2+i)x^i}\\
&=2\sum_{i=1}^{\infty}{\binom{i+1}{2}}x^i
\end{aligned}
$$

これを見るとなんだか負の二項定理が使えそうですね.使えるように変形すると

$$
\begin{aligned}
f&=2\sum_{i=1}^{\infty}{\binom{i+1}{2}x^i}\\
&=2x\sum_{i=0}^{\infty}{\binom{i+2}{2}x^i}\\
&=\frac{2x}{(1-x)^3}
\end{aligned}
$$

となります.ここまでくればあとは一本道です

$$
\begin{aligned}
{[x^M]}f^N&={[x^M]}\left(\frac{2^N x^N}{(1-x)^{3N}}\right)\\
&=2^N{[x^{M-N}]}\left(\frac{1}{(1-x)^{3N}}\right)\\
&=2^N{[x^{M-N}]}\left(\sum_{i=0}^{\infty}{\binom{i+3N-1}{3N-1}x^i}\right)\\
&=2^N\binom{2N+M-1}{3N-1}
\end{aligned}
$$

となり,求める値が $2^N\binom{2N+M-1}{3N-1}$ であることが分かりました.
この値は二項係数のテーブルを前計算しておけば計算できます.
なお,$2N+M-1<2N-1$ の場合などには気を付けてください

### 実装
- https://mofecoder.com/contests/kyoprocamp2023west/submissions/7052

main関数がかなり下です.