---
tags: yukicoder
---
# Don't be Negative! 解説

表記のために $K≠0$ とする
$\displaystyle f=(x^{-M}+\dots+x^M)-x^K-x^{-K}$
$s = f \bmod{(1 - x)} = 2M-1$
として、求めるものは $f^N+2sf^{N-1}+\dots+Ns^{N-1}f$ の $x^{負}$ の項の和

#### ↑について

$X$ の累積和を取ると転倒数
転倒数のペアの間隔ごとに数える
間隔が $1$ のペアは $N$ 個、転倒するのは $f$ の負の部分が選ばれた場合、ペアの外の選び方が $s^{N-1}$ なので $Ns^{N-1}f$
間隔が $N$ のペアは $1$ 個、転倒するのは $f^N$ の負の部分が選ばれた場合、ペアの外の選び方が $1$ なので $f^N$
などとなる

---

\begin{align}
f^N+2sf^{N-1}+\dots+Ns^{N-1}f &= \dfrac{f^N+sf^{N-1}+\dots+s^{N-1}f-Ns^N}{1-\dfrac{s}{f}}\\
&=\dfrac{f^N-(N+1)s^N+Ns^{N+1}f^{-1}}{\left(1-\dfrac{s}{f}\right)^2}\\
&=\dfrac{f^{N+2}-(N+1)s^Nf^2+Ns^{N+1}f}{(f-s)^2}\\
\end{align}

なので、求めるものは

$$
[x^{-1}]\dfrac{f^{N+2}-(N+1)s^Nf^2+Ns^{N+1}f}{(1-x)(f-s)^2}
$$

負の項ができないようにずらす

$F=x^Mf,\ S = x^Ms$ として、求めるものは

$$
[x^{NM-1}]\dfrac{F^{N+2}-(N+1)S^NF^2+NS^{N+1}F}{(1-x)(F-S)^2}
$$

ところで、$S^N = s^{NM}x^{NM}$ なので答えに影響を与えない。よって、
$$
[x^{NM-1}]\dfrac{F^{N+2}}{(1-x)(F-S)^2}
$$

これは、FPS の pow と inv で $\Theta(NM \log (NM))$