HackMDDon'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))\)
