# エイシング プログラミング コンテスト 2020 F - Two Snuke

## 問題リンク
- https://atcoder.jp/contests/aising2020/tasks/aising2020_f

## 解法

形式的冪級数 $F$ を

$$F=\sum_{0\leq i\lt j}{(j-i)x^{i+j}}$$

で定めます. すると, 制約$\leq N$ を$=N$ に変更した場合の答は $[x^N]F^5$ として表せます.

したがって求める答えは $\displaystyle[x^n]\frac{1}{1-x}F^5$ です.

まずは $F$ について整理しましょう.

$i+j=n$ を満たす $0\leq i\lt j$ の組を全て列挙すると

$$(i,j)=(0,n),(1,n-1),\dots,\left(\left\lfloor\frac{n}{2}\right\rfloor,n-\left\lfloor\frac{n}{2}\right\rfloor\right)$$

という風になります.

これらに対する $j-i$ の値は順に $n,n-2,\dots,n-2\left\lfloor\frac{n}{2}\right\rfloor=n\bmod 2$ です.
これは 初項 $n$, 末項 $n\bmod 2$, 項数 $\left\lfloor\frac{n}{2}\right\rfloor+1$ の等差数列ですから, これらの総和である $[x^n]F$ は以下のように書けます.

$$
[x^n]F = \left\{
\begin{array}{ll}
\frac{n}{2}(\frac{n}{2}+1) & (n \text{ is even.})\\
\left(\frac{n+1}{2}\right)^2 & (n \text{ is odd.})
\end{array}
\right.
$$

したがって, $F$ は以下のよう書けます.

$$F=\left(\sum_{n=0}^{\infty}{n(n+1)x^{2n}}\right)+\left(\sum_{n=0}^{\infty}{(n+1)^2x^{2n+1}}\right)$$

それぞれの形式的冪級数を求めます.

### $\displaystyle\left(\sum_{n=0}^{\infty}{n(n+1)x^{2n}}\right)$ を求める

等式
$$\frac{1}{1-x}=\sum_{n=0}^{\infty}{x^n}$$
から導きます.
両辺 $x$ で微分して $x$ 倍すれば
$$
\begin{aligned}
x\cdot\left(\frac{1}{1-x}\right)^{^\prime}&=x\cdot\left(\sum_{n=0}^{\infty}{x^n}\right)^{\prime}\\
\frac{x}{(1-x)^2}&=\sum_{n=0}^{\infty}{nx^n}
\end{aligned}
$$

です. 両辺 $x$ 倍して微分すると

$$
\begin{aligned}
\left(\frac{x^2}{(1-x)^2}\right)^{\prime}&=\left(\sum_{n=0}^{\infty}{nx^{n+1}}\right)^{\prime}\\
\frac{2x}{(1-x)^3}&=\sum_{n=0}^{\infty}{n(n+1)x^n}
\end{aligned}
$$

よって $x$ を $x^2$ で置き換えることで

$$
\sum_{n=0}^{\infty}{n(n+1)x^{2n}}=\frac{2x^2}{(1-x^2)^3}
$$

が得られました.
### $\displaystyle\left(\sum_{n=0}^{\infty}{n^2x^{2n+1}}\right)$ を求める
$1-x$で割る操作が累積和を取る操作に対応するということを思い出すと、

$$\frac{1}{(1-x)^2}=\sum_{i=0}^{\infty}{(n+1)x^n}$$

です. 両辺 $x$倍して微分すれば

$$
\begin{aligned}
\left(\frac{x}{(1-x)^2}\right)^{\prime}&=\left(\sum_{n=0}^{\infty}{(n+1)x^{n+1}
}\right)^{\prime}\\
\frac{1+x}{(1-x)^3}&=\sum_{n=0}^{\infty}{(n+1)^2x^n}
\end{aligned}
$$

です. よって $x$ を $x^2$ に置き換え, $x$ 倍することにより

$$\sum_{n=0}^{\infty}{(n+1)^2x^{2n+1}}=\frac{x(1+x^2)}{(1-x^2)^3}$$

が得られました.

### $F^5$ を求める
以上の結果から,

$$F=\frac{2x^2}{(1-x^2)^3}+\frac{x(1+x^2)}{(1-x^2)^3}=\frac{x(1+x)^2}{(1-x^2)^3}$$

となります. よって,
$$F^5=\frac{x^5(1+x)^{10}}{(1-x^2)^{15}}=\frac{x^5}{(1+x)^{5}(1-x)^{15}}$$

となり,

$$\frac{1}{1-x}F^5=\frac{x^5}{(1+x)^5(1-x)^{16}}$$

となります.

### $\displaystyle[x^N]\frac{1}{1-x}F^5$ を求める
先ほどの結果から, $\displaystyle\frac{1}{1-x}F^5$ は $\displaystyle\frac{P}{Q}$ という形で表示できます.
この形のFPSの$N$次の項はBostanMori法により $O(K\log K\log N)$-timeで求められることが知られています($\deg P,Q\leq K$).
よって, これを使うことでこの問題は $O(N\log N)$時間で解けました.

### 提出
- https://atcoder.jp/contests/aising2020/submissions/54482365

$\bmod$ が $10^9+7$ であることに注意してください. FFTによる畳み込みが使えないので, 愚直に行う必要があります.

### OEISの利用

$$
[x^n]F = \left\{
\begin{array}{ll}
\frac{n}{2}(\frac{n}{2}+1) & (n \text{ is even.})\\
\left(\frac{n+1}{2}\right)^2 & (n \text{ is odd.})
\end{array}
\right.
$$

の部分ですが, 先頭10項ぐらい求めてOEISに入力すればすごく楽です.