牛頓迭代實現多項式半家桶及其常數優化——2025.6.15鮮花

なんでそんなこと言い出すの
あたし何も悪くないよ
きみが好きを始めたのに
あたしそれを信じたのに
きみのためになんでもしたのに
きみ以外で幸せ
なれっこないんだもん
そこんところ
きみはどう思ってるの
さあ一緒にいこう？ネバーランド
何度でもきみと遊びたい
バイバイ言ったら死刑なルール
絶対誰にも渡さない
嗚呼こんなに甘いネバーランド
どうしてきみはつらそうなの？
どんまい？ 飽いたらリセットルール？
どうしてもきみが離れない
まだ好きだよね？
バッドなエンドだ あっはっは
無理すぎて
あれもこれも病んじゃった
キュートな愛も無駄
「重すぎてしんどい」って
泣いちゃった
バッドなエンドだ あっはっは
無理すぎて
あれもこれも病んじゃった
キュートな愛も無駄
「重すぎてしんどい」って
泣いちゃった
変な冗談は良くないかも
噓と言ってお互いのために
きみが好きを始めたのに
あたしそれを信じたのに
きみのためになんでもしたのに
あたし以外で幸せ
なれっこないでしょ？
ありえないよ 笑えない
許してやんない
さあ一緒にいこう？ネバーランド
「最後」とかなんで？認めない
頂戴でっかいごめんのポーズ
なんとかやり直せるんじゃない？
終わっちゃうくらいなら
嫌いにさせてよ
これ以上
あたしに優しくしないでよ
だって好きって思ってしまうもん
ずっと一緒願ってしまうもん
やっぱ全部きみが悪いんだ
じゃあ一緒に死のう？ネバーランド
何度でもきみで拗れたい
最強ふたりの未來のルーム
絶対誰にも渡さない
嗚呼こんなに甘いネバーランド
やっときみも笑えるんだね
天才 あたしの想いがルール
最後に愛は勝つ そうでしょう？
ハッピーエンドだ あっはっは
これからもきみがすきなんだった
嫉妬も酸素もバイバイ
これからもだいすきなんだった
ハッピーエンドだ あっはっは
これからもきみがすきなんだった
嫉妬も酸素もバイバイ
これからもだいすきなんだった
あは

卡了一天半的常的結果，其實挺好玩的。

首先會一下牛頓迭代。

我們有一個非平凡函數 \(G(x, y)\)，求模 \(x ^ n\) 意義下的 \(f(x)\) 滿足 \(G(x, f(x)) \equiv 0 \pmod {x ^ n}\)

我們先把 \(n\) 補齊到 \(2 ^ k\)。

考慮倍增，若我們已經求出模 \(x ^ n\) 意義下的 \(f_0\)，考慮求出模 \(x ^ {2n}\) 意義下的 \(f\)。

將 \(G(x, f)\) 在 \(f = f_0\) 處泰勒展開，有：

考慮到 \(f - f_0\) 的最低次項是 \(n\)，則 \(i \ge 2\) 時其值模 \(x ^ {2n}\) 為 \(0\)。所以原式等價于：

然后就做完了。

具體的式子可以看 oi-wiki

考慮優化常數，這里大量參考 negiizhao 的 uoj 博客，但只寫了其中比較淺顯的一點，更深的可以看原文章。

以下統一設 \(k_0\) 表示上次迭代 \(k\) 的結果，\(k\) 表示本次迭代或真實值，\(\hat{g^n}\) 表示 \(g\) DFT 以后的長為 \(n\) 的點值，將 DFT 操作和 IDFT 操作統稱為 FFT 操作，簡稱 FFT。

實際實現中存在很多的 FFT 復用，這里我們假設一個 FFT 的結果求出來后就會一直使用。

設一次大小為 \(n\) 的 FFT 的代價是 \(E\)，將 FFT 的常數視為線性的。

由于我的疏忽，可能會有算錯的，還請指正。

1. 求逆，\(g = \frac 1f\)：

   式子：\(g = 2g_0 - g_0^2f\)

   容易發現對于 \(g_0^2f\) 我們要做一次大小是 \(2n\) 的卷積，一次大小是 \(4n\) 的卷積，總計 \(18E\)。

   我們有技巧可以用 \(2E\) 的代價從 \(\hat{g^n}\) 求 \(\hat{g^{2n}}\)，從而使代價降到 \(16E\)。這個技巧將會在 Bostan-Mori 的時候講到，這里我們有更好的辦法。

   發現 \(g_0f\) 的前 \(n\) 項只有常數項是 \(1\)，所以我們拆一下式子：\(g = 2g_0 - g_0^2f = g_0 - (fg_0 - 1)g_0\)，這樣 \(fg_0 - 1\) 的系數在 \([n, 3n)\)，則可以直接做 \(2n\) 的循環卷積，同樣的 \((fg_0 - 1)g_0\) 也可以做 \(2n\) 的循環卷積，注意中間有清空操作，所以總代價為 \(10E\)。

2. 開根，\(g = \sqrt f\)：

   式子：\(g = \frac {g_0}2 + \frac f{2g_0}\)，暴力做需要 \(2n\) 的求逆和 \(4n\) 的卷積，總計 \(22E\)。

   類似求逆的優化，我們吧式子展開成 \(g_0 - \frac{g_0 ^ 2 - f}{2g_0}\)，此時 \(g_0 ^ 2 - f\) 是 \(2n\) 的循環卷積，\(\frac{g_0 ^ 2 - f}{2g_0}\) 依然是 \(2n\) 的循環卷積。注意到 \(g_0 ^ 2 - f\) 最低次項是 \(n\)，則 \(\frac 1{2g_0}\) 只需要求 \(n\) 項，總計 \(18E\)。

   我們接著發現，\(g_0 ^ 2 - f\) 的系數竟然是 \([n, 2n)\)，也就是說可以換成長為 \(n\) 的循環卷積，總計 \(13E\)。

   注意這個結果要將求逆展開來和開根一起迭代進行 FFT 結果的復用。

   注意到開根迭代的 FFT 結果中有一個可以和下一輪迭代復用，最終是 \(12E\)。

3. 求商或求 \(\ln\)，\(h = \frac fg\)：

   \(\ln f = \int \frac{f'}f\)，其中求導和積分都是 \(\mathcal{O}(n)\) 的，所以和求商等價。

   暴力做是求逆加 \(4n\) 的卷積，總計 \(22E\)

   依然是展開：\(h = h_0 - \frac{gh_0 - f} f\)，類似開根用循環卷積優化，代價是 \(15E\)，類似的，需要將求逆展開來和開根一起迭代。

   有一個技巧是通過 \(\hat{g_0}\) 快速求出 \(fg\)，具體就是將 \(g\) 拆開，懶得寫了。

4. 指數，\(g = \exp f\)

   式子：\(g = g_0(1 - \ln g_0 + f)\)。

   暴力做是 \(\ln\) 加 \(4n\) 卷積，總計 \(27E\)

   考慮拆式子，我們拆成 \(g = g_0 - g_0\int{(\frac{g_0'}{g_0}-f')}\)

   我們發現這次的 \(\frac 1{g_0}\) 是在 \(2n\) 次截斷，所以沒法將求逆展開來和開根一起迭代，只能暴力做，但是循環卷積依然一樣做，代價是 \(22E\)。

   我們繼續推式子，設 \(h_0 = \frac 1{g_0} \bmod x ^ n\)：

   \[\begin{aligned} g \bmod x^{2n} &= g_0 - g_0(\int{(\frac{g_0'}{g_0})}-f) \bmod x^{2n} \\ &= g_0 - g_0\int{(\frac{g_0'}{g_0}-f')} \bmod x^{2n} \\ &= g_0 - g_0\int{(g_0h_0(\frac{g_0'}{g_0}-f'))} \bmod x^{2n} \\ &= g_0 - g_0\int{(g_0'h_0-f'-(g_0h_0-1)f_0')} \bmod x^{2n} \end{aligned}\]

   這里面較為關鍵的一步是發現 \(\frac{g_0'}{g_0}-f'\) 的系數 \(\ge n - 1\)，則 \(g_0h_0(\frac{g_0'}{g_0}-f') \equiv \frac{g_0'}{g_0}-f' \pmod {x ^ {n - 1}}\)，積一下就是 \(\int(g_0h_0(\frac{g_0'}{g_0}-f')) \equiv \int(\frac{g_0'}{g_0}-f') \pmod {x ^ n}\)。

   這里的 \(g_0'h_0-f'\) 和 \(g_0h_0-1\) 都可以 \(n\) 循環卷積，\((g_0h_0-1)f_0'\) 是 \(n ^ 2\) 循環卷積 \(g_0\int{(g_0'h_0-f'-(g_0h_0-1)f_0')}\) 是 \(n ^ 2\) 循環卷積，將求逆展開來和開根一起迭代，依然有一個 FFT 結果可以對下輪復用。

   發現 \(g_0h_0-1 \to (g_0h_0-1)f_0'\) 這一步中有一個將前一半多項式移到后一半，這個可以先二倍點值在暴力吧點值乘上 \(x^k\)，代價可以做到 \(2E\)。

   如何二倍點值見 Bostan-Mori 部分。

   實現下來代價是 \(19E\)

5. Bostan-Mori

   本段參考 EI 一種新的線性遞推計算方法

   先會一下 Bostan-Mori，求 \([x^k]\frac {F(x)}{Q(x)}\)，考慮：

   \[[x^k]\frac {F(x)}{Q(x)} = [x^k]\frac {F(x)Q(-x)}{Q(x)Q(-x)} \]

   我們發現 \(Q(x)Q(-x)\) 只有偶次項，而 \(F(x)Q(-x)\) 隨 \(x\) 的奇偶只會有奇次項或偶次項有用，于是折半即可，設多項式長度是 \(n\)，容易發現多項式長度不會變。復雜度是 \(n\log n\log k\)。

   樸素做代價是 \(10E\)，這里記 \(F = F(x), A = Q(x), B = Q(-x)\)

   首先的一個技巧是 \(\hat{A_i} = \hat{B_{i \oplus \frac n2}}\)，所以可以省掉 \(B\) 的一遍 \(2n\) 的 FFT。

   然后考慮如何在點值上提取奇偶次冪。以偶次為例，奇次是類似的。我們設 \(C_i = \frac {A_i + (-1) ^ i A_i}2\)，則 \(\hat{C_i} = \frac {\hat{A_i} + \hat{A_{i \oplus \frac n2}}}2\)，只要取 \(\hat{C_i}\) 的前一半即可。

   最后就是如何直接推出二倍點值，這也是容易的

   \[\hat{A^{2n}_2k} = \hat{A_k} \]
   \[\hat{A^{2n}_{2k + 1}} = \sum_i\hat{\omega_{2n}^i A_i}\omega_{2n}^{ik} \]

   因此我們先 IDFT 得到 \(A\)，再乘 \(\omega_{2n}^{i}\)，在做 DFT 即可。

   最后就只有 \(4E\)。

具體的實現可以看我板子（寫的很屎）。