谔谔
by OItby @ 2020-03-05 21:31:18
我的NTT似乎不曾那么写过？
by Smile_Cindy @ 2020-03-05 21:32:28
感觉应该是邪门歪道吧，但写了那么多次到现在才出问题，挺吃惊的（~~不相信这个世界了~~）
by 辰星凌 @ 2020-03-05 21:33:41
NTT我没那么写过啊
by Lithium_Chestnut @ 2020-03-05 21:36:05
我不是问泥萌有没有那么写过，而是想知道这样做的正确性/错误性何在，为啥过了若干道题
by 辰星凌 @ 2020-03-05 21:37:13
@[辰星凌](/user/110985) 您具体通过了哪一道题啊
by iostream @ 2020-03-05 21:49:00
@[iostream](/user/13052) [分治fft板子](https://www.luogu.com.cn/record/31077506)
下面这四个代码都差不多：
[残缺的字符串](https://www.luogu.com.cn/record/31124740)
[kmp板子](https://www.luogu.com.cn/record/31123109)
[CF528D](https://www.luogu.com.cn/record/31127671)
[DNA](https://www.luogu.com.cn/record/31128450)
by 辰星凌 @ 2020-03-05 21:53:53
@[iostream](/user/13052) [还有这个，也是分治fft](https://www.luogu.com.cn/record/31364924)剩下的20pt是超时，正解多项式求逆
by 辰星凌 @ 2020-03-05 21:55:59
@[辰星凌](/user/110985) 我知道了
by iostream @ 2020-03-05 21:56:09
@[辰星凌](/user/110985) 这个东西是循环卷积优化多项式乘法，你考虑当你 $len=n$ 和 $len=m$ 的多项式乘法，在 $n<2^t<2n$ 的情况下做多项式乘法产生循环卷积。
如果你最后只要用多项式 $x^m\sim x^n$ 的值的话，可以知道循环卷积尽管溢出但不影响这些位置的值（最多到达 $x^{m-1}$ 的地方）。
by iostream @ 2020-03-05 21:58:41