按时间排序的第一页题解里除了第一篇和 Karry5307 那篇之外没有一篇是完全写对的。
以下是三种 Hack 的方式:
- 第一,许多题解没有考虑到这样一个问题,即:在读入时已经对 n,m 取模,导致它们的值至少一个为 0。故如果对快速幂传入的指数不作 +mod 处理就会导致死循环。
- 第二,事实上如果出现了负数,那么在快速幂的循环中限定指数大于零即
for(;y>0;y>>=1) 也是不正确的。
- 第三,a 和 c 不一定同时为 1 或不为 1。已有的 Hack 数据就已经 Hack 了这种情况(按时间排序的第四、五、七、八、十题解 )。
以上三种情况分别 Hack 了:
- 按时间排序的第二、三、四、八、十篇题解。
- 按时间排序的第五、六、七篇题解。
- 按时间排序的第四、五、七、八、十题解。
最后,第三篇题解被 UOJ 上的数据 Hack 了,但我没看懂题解的代码;第六篇题解似乎无法通过后 50 分。
事实上判断 mod 是 p 还是 p−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。