该题的三类 Hack:大部分题解的错误
查看原帖
该题的三类 Hack:大部分题解的错误
246979
SalomeJLQ楼主2023/10/29 14:48

按时间排序的第一页题解里除了第一篇和 Karry5307 那篇之外没有一篇是完全写对的。

以下是三种 Hack 的方式:

  1. 第一,许多题解没有考虑到这样一个问题,即:在读入时已经对 n,mn,m 取模,导致它们的值至少一个为 00。故如果对快速幂传入的指数不作 +mod+mod 处理就会导致死循环。
  2. 第二,事实上如果出现了负数,那么在快速幂的循环中限定指数大于零即 for(;y>0;y>>=1) 也是不正确的。
  3. 第三,aa 和 cc 不一定同时为 11 或不为 11。已有的 Hack 数据就已经 Hack 了这种情况(按时间排序的第四、五、七、八、十题解 )。

以上三种情况分别 Hack 了:

  1. 按时间排序的第二、三、四、八、十篇题解。
  2. 按时间排序的第五、六、七篇题解。
  3. 按时间排序的第四、五、七、八、十题解。

最后,第三篇题解被 UOJ 上的数据 Hack 了,但我没看懂题解的代码;第六篇题解似乎无法通过后 50 分。

事实上判断  mod \bmod 是 pp 还是 p−1p-1,正确的写法应该是这样:

A=Tpow(A,((a==1?m1:m2)-1+(a==1?mod:mod-1))%(a==1?mod:mod-1)),A=A*B,
A=Tpow(A,((A.a[0][0]==1?n1:n2)-1+(A.a[0][0]==1?mod:mod-1))%(A.a[0][0]==1?mod:mod-1));
B.a[0][0]=a,B.a[1][0]=b,B.a[1][1]=1;
B=Tpow(B,((a==1?m1:m2)-1+(a==1?mod:mod-1))%(a==1?mod:mod-1)),A=A*B;

以上三种类型的 Hack 数据分别是 UOJ Extra Test #4、UOJ Extra Test #6、Luogu Subtask #1 & UOJ Extra Test #3。

2023/10/29 14:48
加载中...