半在線卷積與全在線卷積

乙女解剖であそぼうよ
ドキドキしたいじゃんか誰だって
恥をしたい
痛いくらいが良いんだって知った
あの夜から
こんばんは 今平気かな?
特に言いたいこともないんだけど
もうあれやこれや浮かぶいいな
君が居なくちゃどれでもないや
仮面同士でイチャついてら
寸寸 戀と表記せず
気持ち vs 退屈は PK戦
そうなにもかもに迷子がおり
淚流して SOS を
半目開きで娘娘する
病事も全部 君のもとへ添付
ツライことほど分け合いたいじゃない
この好きから逃げたいな
やっぱぱぱ
乙女解剖であそぼうよ
本當の名前でほら呼び合って
生きたくない
そう言えばいいんだった
楽になれるかな
乙女解剖であそぼうよ
ドキドキしたいじゃんか誰だって
恥をしたい
痛いくらいが良いんだって知った
あの夜から
こんな早くにごめんね
起こしちゃったよね
今 大丈夫
君が別の人のことを
好きになるって夢を見たんだ
否定してほしい ねえ愛して
朝と夜2回分
君に撒くスパイス
思い込みの狂気
効果はない
ねえ 最近冷たいね
やっぱぱぱ
乙女解剖であそぼうよ
身を焦がす感情をヌき合って
もうバカみたい
嫌々がたまんないの
誤解は解けるかな
乙女解剖であそぼうよ
涎をバケットの上に涂って
確かめよう
期待外れ最高潮だった
あの夜から
乙女解剖であそぼうよ
本當の名前でほら呼び合って
生きたくない
そう言えばいいんだった
楽になれるかな
乙女解剖であそぼうよ
ドキドキしたいじゃんか誰だって
恥をしたい
痛いくらいが
良いんだって知った
あの夜みたいに

水一篇鮮花，其實是為以后鮮花做準備。

不會寫 \(\frac{n\log^2 n}{\log\log n}\) 的，回了就補。

感覺半在線卷積還是比牛頓迭代可寫。

1. \(F = \frac 1G\)

   這個系數比較好做，直接展開移項即可。

   \[FG = 1 \]
   \[G_0F_n = -\sum_{i = 0}^{n - 1}F_iG_{n - i} \]

2. \(F = \exp G\)

   求導：

   \[F' = G'F \]

   兩邊提取 \(n - 1\) 次項，有：

   \[nF_n = \sum_{i = 0}^{n - 1}(n - i)F_iG_{n - i} \]

3. \(F = \ln G\)

   類似 \(\exp\) 求導：

   \[F'G = G' \]

   兩邊提取 \(n - 1\) 次項，移項，有：

   \[nF_n=nG_n-\sum_{i=0}^{n-1}iF_iG_{n-i} \]

實現的時候需要注意什么時候乘上什么。具體可以看代碼。

乘法逆提交記錄 | exp提交記錄 | ln提交記錄。

根號和冪直接 \(\ln+\exp\) 即可。

全在線卷積，設 \(c_k = \sum\limits_{i + j = k} a_ib_j\)，其中 \(a,b\) 在線給出（一個簡單的例子是 \(a_n = \sum\limits_{i = 0}^{n - 1} a_ia_{n - i}\)）：

其實非常的簡單，先做前一半，考慮對后一半的貢獻。對于 \(i,j \le \frac n2\)，就是一個普通卷積；對于 \(i \le \frac n2, j > \frac n2\) 和 \(j \le \frac n2, i > \frac n2\)，是兩個半在線卷積。

于是復雜度是：\(T(n) = T(\frac n2) + S(n)=\mathcal{O}(S(n))\)，其中 \(S(n)\) 是半在線卷積復雜度。