P4245 【模板】任意模數多項式乘法

https://www.luogu.com.cn/blog/AzusaCat/solution-p4245
首先這類問題指的是對于一個非NTT模數，我們如何計算多項式乘法，對于NTT不容易找到單位根，對于FFT又會爆精度。

方法1：三模數NTT
尋找三個大模數最后CRT合并即可

方法2：MTT
將系數拆分為兩部分，分別是M的倍數和余數，然后我們只需要對其分別處理即可，但是這樣暴力的做一共需要7次FFT復雜度太高，我們通過一些數學技巧可以優化到4次。

首先DFT時可以發現虛部是空的，我們可以將另一個多項式放在虛部，然后利用共軛求解共軛的值，然后就可以一次求出兩個多項式的點值，所以可以將4次DFT變為2次。

然后IDFT時，發現點值最后轉化為系數時虛部也是空的，所以我們可以將兩個多項式加在一起IDFT，可以發現如果給系數乘i，那么點值對應乘i，所以對應的虛部點值不會影響到實部的系數。

代碼細節：

取整問題
floor是向下取整
ceil是向上取整
強制轉換是向0取整
所以我們要四舍五入需要判斷正負，對于負數-0.5后取整，對于正數+0.5后取整。

這里需要維護的complex操作太多了，自己寫結構體太麻煩了，還是直接用complex庫里封裝好的類型吧。

我暈了啊，竟然是一開始讀入時候M設置為根號n了，天哪，怪不得會爆掉

還有一個小細節，就是原來fft里可以不用設置為-sin，直接最后或者一開始的時候reverse就好了，因為這樣也相當于將其設置為-k

記得一旦有乘法就要檢查是否會爆int，有些時候我們不得不先除后乘，否則就會爆掉。

總結

以上是生活随笔為你收集整理的P4245 【模板】任意模数多项式乘法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。