# yukicoder No.2485 Add to Variables (Another)

## 問題

[No.2485 Add to Variables (Another)](https://yukicoder.me/problems/no/2485)

## 解説

操作のうち $A_N$ が増加するのは下二つのみであるから，それらは合わせて $B_N$ 回行われる${}:(\star)$．

数列 $X=(X_1,\dots,X_N)$ を $X_1=A_1,X_i=A_i-A_{i-1}\ (2\leq i\leq N)$ で定め，$A$ に対する各操作を $X$ に対して言い換えると次のようになる．

- 何もしない．
- 整数 $k\ (1\leq k\leq N-1)$ を選び，$X_1$ に $1$ を，$X_{k+1}$ に $-1$ を足す．
- 整数 $k\ (2\leq k\leq N-1)$ を選び，$X_k$ に $1$ を足す．
- $X_1$ に $1$ を足す．

上二つ/下二つをまとめて次のようになる．

- 整数 $k\ (1\leq k\leq N)$ を選び，$X_1$ に $1$ を，$X_k$ に $-1$ を足す．
- 整数 $k\ (1\leq k\leq N-1)$ を選び，$X_k$ に $1$ を足す．

$(\star)$ より一つ目の操作は $M-B_N$ 回行われるから，数列 $C=(C_1,\dots,C_N)$ を $C_1=B_1-(M-B_N),C_i=B_i-B_{i-1}\ (2\leq i\leq N)$ で定めると，$X=(0,\dots,0)$ に対し次のいずれかの操作を $M$ 回行って $X=C$ とする方法の数を求めればよい．

- 整数 $k\ (1\leq k\leq N)$ を選び，$X_k$ に $-1$ を足す．
- 整数 $k\ (1\leq k\leq N-1)$ を選び，$X_k$ に $1$ を足す．

その値は形式的冪級数を用いれば次のように表現できる（多項係数を考える）．
\begin{align*}
[x^M]M!\prod_{k=1}^{N}\sum_{i\geq 0}\frac{1}{i!(i+|C_k|)!}x^{2i+|C_k|}
\end{align*}

これは計算量 $O(NM\log M)$ で計算できる．なお[(Another)でない方](https://yukicoder.me/problems/no/2484)もこれで通る．