请求增强数据

rogeryoungh @ 2024-01-02 14:11:49

by rogeryoungh @ 2024-01-02 14:21:55

大部分题解区的 4 次、5 次 FFT 优化，基本精度都不够高。

请注意 yosupo 的 n, m 有微小的不同，不需要加一。

by rogeryoungh @ 2024-01-02 14:23:57

@小粉兔 @chen_zhe

by masterhuang @ 2024-01-20 10:35:36

模板题精度足够做绝大多数题了，这样没必要。

不然许多题用到的 hash 也是都能hack的呢

by UnyieldingTrilobite @ 2024-02-02 09:36:09

@masterhuang 就是因为这是模板题才要死扣各种细节啊。

by masterhuang @ 2024-02-02 12:56:55

@UnyieldingTrilobite 这不是相当于逼大家都写三模NTT？

要知道绝大多数人写三模跑不过MTT的，为这点精度增大常数没必要。

MTT的精度甚至实现精细开double都在绝大多数情况下够用，抠细节没意义，如果这样建议你先整治你谷的网络流题呢，看看哪个更松

by UnyieldingTrilobite @ 2024-02-02 13:05:45

@masterhuang 所以网络流出了正常版和数据加强版啊。

如法炮制不是很好嘛。

by masterhuang @ 2024-02-02 13:19:31

@UnyieldingTrilobite 我的建议是最多放个私题并帖题目上，卡MTT精度很难蚌。

你要知道，大部分人三模的写法总时长至少是楼主的3~4倍，所以MTT写法（学4~5次DFT的）的推广还是很有必要的，比一般三模快很多。

而且我所做过的所有任意模数的题目MTT精度是绝对够的，不会有人卡的，所以放MTT精度略劣的写法过是合乎情理的。

网络流的“加强版”是因为HLPP，而不是区分dinic实现细节是否有误（

by rogeryoungh @ 2024-02-14 17:55:24

@masterhuang 精度并不是 略劣。单次 FFT 的误差增长上界（Link）是 O(\log n)，据此算得在 n = 2^{17} 下卷积输入 a 应该小于 10903；若取 a = 2^{15} 则误差是 9.03。

再考虑单位根，很多实现采用迭代乘法来避免 \sin, \cos 的计算，单位根的误差增长是 O(\sqrt{n}) 甚至 O(n)；另外，8 次 FFT 到 4 次 FFT 的优化也对精度有一定损耗。

总之 3 拆 FFT 大概就足够精确了，实现的不好的 2 拆误差达到成百上千也不是很奇怪。

我非常同意 @UnyieldingTrilobite 的意见，模板题更应该在其标明的数据范围无懈可击。本模板题声明了 a_i \leqslant 10^9，就应该尝试卡掉此范围错误的提交。

或者可以把数据放小点。比如 P3803 多项式乘法，其数据范围 a \in [0, 9] 就对 FFT 友好了。

by masterhuang @ 2024-02-14 18:14:04

@rogeryoungh 你说的对，可是“三拆”是指啥？

by rogeryoungh @ 2024-02-14 18:19:09

@masterhuang

• 不拆：123456
• 二拆：123，456
• 三拆：12，34，56

一般大伙写的都是 2 拆 FFT。