ABC321-FをFPSで考えると、結局どうなる？（冗長版）

ABC321-FはFPSで考えればいい、ということはわかって、その結果が配ったDPを逆に戻してあげればいいということもわかったのだけれど、いまいち理解が不足していたので、ちゃんと行間を埋めてみました。備忘録です。
なお、基本的なことは全て maspy さんの記事「[多項式・形式的べき級数]（２）式変形による解法の導出」に書いてあって、こちらで勉強しました。ありがとうございます。

+ d

FPSで考えれば、「+ d」は形式的べき級数 $${f(x)}$$ に $${1 + x^d}$$ を掛算することになる。$${f(x)=\sum_{i=0}^\infty a_i x^i}$$ として、

$$
\begin{aligned}
f(x)(1+x^d) &= \left( \sum_{i=0}^\infty a_i x^i \right) \left( 1+x^d \right) \\
&= \sum_{i=0}^\infty a_i x^i + \sum_{i=0}^\infty a_i x^{i+d} \\
&= \sum_{i=0}^{d-1} a_i x^i + \sum_{i=d}^\infty (a_i + a_{i-d}) x^i \\
\end{aligned}
$$

$${f(x)}$$ を表す数列を A[i] 、$${ f(x)(1+x^d) = g(x)}$$ として $${g(x) = \sum_{i=0}^\infty b_i x^i}$$ を表す数列を B[i] とすれば、

$$
\begin{aligned}
b_i = \begin{cases}
a_i & (i < d) \\
a_i + a_{i-d} & (d <= i)
\end{cases} \end{aligned}
$$

よって

for(int i = 0; i <= K; i++) B[i] = (i < d ? A[i] : A[i] + A[i - d]);

で達成できる。

- d

-dの方はちょっとややこしい。 -d をするということは、過去に挿入したdを削除するということなので、形式的べき級数的には $${(1+x^d)}$$ で割れば良い。つまり、$${f(x)/(1+x^d) = g(x)}$$ をすればよい。

で、この式を $${g(x)(1+x^d) = f(x)}$$ と分母を払ってから、A[i] と B[i] との関係を逆向きに動かす、つまり、

$$
\begin{aligned}
g(x)(1+x^d)
&= \sum_{i=0}^{d-1} b_i x^i + \sum_{i=d}^\infty (b_i + b_{i-d}) x^i \\
\end{aligned}
$$

としておいて、

$$
\begin{aligned}
a_i = \begin{cases}
b_i & (i < d) \\
b_i + b_{i-d} & (d <= i)
\end{cases} \end{aligned}
$$

だから、$${i}$$ を小さい方から決めていけば$${a,b}$$ を逆にして

$$
\begin{aligned}
b_i = \begin{cases}
a_i & (i < d) \\
a_i - b_{i-d} & (d <= i)
\end{cases} \end{aligned}
$$

と、既に決まった $${b_{i-d}}$$ を使って $${b_i}$$ を決めていくことができて、

for(int i = 0; i <= K; i++) B[i] = (i < d ? A[i] : A[i] - B[i - d]);

で達成できる。

ところが、この遷移は逆回しで考えるので、なんだかキツネにつままれたような気がする。ちゃんと $${f(x)}$$ から $${g(x)}$$ 方向へ遷移させたい。

そこで、$${(1+x^d)}$$ で割るというのを次のように変形する。

$$
\begin{aligned}
\frac{1}{(1+x^d)} &= \frac{(1-x^d)}{(1+x^d)(1-x^d)}
= \frac{(1-x^d)}{(1-x^{2d} )}
\end{aligned}
$$

すると、$${(1-x^d)}$$ を掛ける方は（$${f(x)(1-x^d)=h(x)=\sum c_i x^i}$$ として）

$$
\begin{aligned}
c_i = \begin{cases}
a_i & (i < d) \\
a_i - a_{i-d} & (d <= i)
\end{cases} \end{aligned}
$$

また、$${(1-x^{2d})}$$ で割る方は、$${1+x^{2d}+x^{4d}+x^{6d}+…}$$ を掛けることになり、これは $${2d}$$ 個離れた累積和なので、

$$
b_i = \begin{cases}
c_i & (i < 2d) \\
c_i + b_{i-2d} & (2d <= i)
\end{cases}
$$

 となる。両方を合わせると、

$$
b_i = \begin{cases}
a_i & (i < d) \\
a_i - a_{i-d} & (d \le i < 2d) \\
a_i - a_{i-d} + b_{i-2d} & (2d \le i)
\end{cases}
$$

で、実装は

for(int j = 0; j <= K; j++){
    B[j] = (j < d ? A[j] : (j < 2 * d ? A[j] - A[j-d] : A[j] - A[j-d] + B[j-2*d]));
}

となる。累積和をとる操作が右辺に$${\{b_i\}}$$ を入れてしまうので、結局最初の逆向きに動かす方法と同じ（よかさらに複雑）なのだけれど、順方向しか考えていないということで、気持ち悪さは軽減された。

- d （再）

と、ここまで考えたところで、$${(1+x^d)}$$ で割るということは、

$$
\frac{1}{(1+x^d)}=1-x^d+x^{2d}-x^{3d}+…=\sum_{i=0}^\infty (-1)^ix^{id}
$$

を掛けることと同じであることに気づきました。これはつまり、$${d}$$ 個離れて毎回反転しながら累積和をとることと同じになる。例えば $${b_0 = a_0}$$ だが、この $${a_0}$$ が反転して累積されて、$${b_d}$$ に入る、つまり、$${b_d = a_d - (b_0 = a_0)}$$ になって、それがさらに次の$${d}$$ 進んだところでまた反転して $${b_{2d} = a_{2d} - (b_d = a_d - a_0)}$$ になって・・・

すると結局、

$$
\begin{aligned}
b_i = \begin{cases}
a_i & (i < d) \\
a_i - b_{i-d} & (d <= i)
\end{cases} \end{aligned}
$$

となり、一番最初の（私的には）違和感のあった式は、実は反転しながら累積和しているだけだった、ということがわかって、気持ち悪さも無くなりました。