请求增强数据

P4245 【模板】任意模数多项式乘法

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

本题大部分通过的提交都无法通过 yosopo 的题目。

尽管大家都已经考虑了拆系数来提高精度,但精度实际上还是不够的,能够被卡掉。

因此请求加强数据。

yosupo 的数据和生成器是 Apache 2.0 开源的,声明版权即可取用。

能不能也让洛谷模板题数据开源

  • https://judge.yosupo.jp/problem/convolution_mod_1000000007
  • https://github.com/yosupo06/library-checker-problems/tree/master/math/convolution_mod_1000000007

by masterhuang @ 2024-02-14 18:24:01

@rogeryoungh 可是3拆你要几次FFT啊?常数不得上天?


by rogeryoungh @ 2024-02-14 18:44:05

@masterhuang 这就是数据范围 1e9 的代价(


by masterhuang @ 2024-02-14 18:49:06

@rogeryoungh 你想想如果你卡了这个那题解里不得全剩常数大的一批的三模NTT,而且你想想对于一个初学者怎么找到能MTT卡过这题的办法?

卡掉后要先想想后果咋处理,不然就缩小数据范围吧。


by rogeryoungh @ 2024-02-14 20:19:57

@masterhuang 仔细想了想,我认为还是得把 2 拆卡掉,错误的做法可能导致部分出题人错估时限,错估代码量,就此以讹传讹的错下去了。

FFT 硬过也没那么复杂,这题时限 2 秒,3 拆也就十几次不至于过不了,我写着玩的一种实现 也可以。

把旧做法卡掉,会有人来写新做法题解的,相信社区(


by masterhuang @ 2024-02-14 20:26:22

@rogeryoungh 无所谓,管理不会动手。我建议是开私题放题面上。要知道你卡了至少2/3的提交都会寄,这影响太大了,我只能说这样的误差在做题中是可以接受的。


by Spasmodic @ 2024-06-24 15:07:02

@chen_zhe


上一页 |