rt,除了两篇没有给出完整代码的题解,其它题解的代码均存在 hack 数据:
https://www.luogu.com.cn/article/t6o2g9x0: WA
(a-10^8-7)*(a-1)
1
a-10^8-7
https://www.luogu.com.cn/article/9s4ubbd2: TLE
(a+1)^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9
1
(a+1)^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9
https://www.luogu.com.cn/article/obgelhhr: RE
1
1
1
https://www.luogu.com.cn/article/3sm8wp4d: WA
(x-3)*(x-7)*(x-13)*(x-10)
1
(x-3)*(x-7)*(x-13)*(x-10)
https://www.luogu.com.cn/article/9bfg4po1: WA
(x-17)*(x-29)*(x-20)
1
(x-17)*(x-29)*(x-21)
https://www.luogu.com.cn/article/utzhmvrw: RE
(x-1231)*(x-20)
1
(x-1231)*(x-21)
https://www.luogu.com.cn/article/r873pk09: TLE
(x-41)*(x-71)*(x-83)*(x-91)*(x-101)*(x-20)
1
(x-41)*(x-71)*(x-83)*(x-91)*(x-101)*(x-21)
https://www.luogu.com.cn/article/zwtdzgzp: WA
2^9^9^9
1
2^9^9^8
https://www.luogu.com.cn/article/aycggv34: WA 代码里都是特判的数据,这种题解怎么过审的。。。
https://www.luogu.com.cn/article/d2y7bv9o: RE
(x-131)*(x-20)
1
(x-131)*(x-200)
https://www.luogu.com.cn/article/5cp1cgjp: RE
10^9+7
1
(10^9+7)*2
https://www.luogu.com.cn/article/rtvcti9s: WA
2^9^9
1
2^8^8
https://www.luogu.com.cn/article/zgfqqv4g: WA
10^8+7
1
(10^8+7)*2
https://www.luogu.com.cn/article/8zd0925f: WA
2^9^9
1
2^8^8
以上的 hack 主要有两种思路,第一种是从代入的值的角度直接构造多项式,第二种是从模数的角度构造大数。
注意到例如我这里列出的最后一个(即题解区第一篇)使用了比较稳定的做法但是没有进行取模导致可以轻松卡掉,而所有题解的模数都是固定的,所以都可以用类似方法卡掉。
解决办法是类似于哈希的时候防止被针对 hack,要不然就设计比较多的模数使得 hack 起来较为困难,要不然就找一些不固定的随机种子并随机一个数作为模数。这时可以选择检查系数,也可以选择代入较多的值。
不过有几个代码我都还没准备 hack 它就先 RE 了。。。