注意,本题如果你使用的类似辗转相除法原理的消元,那么这种写法可能会导致你的部分 TLE:
for(int j=i+1; j<n; ++j) while(Mat[j][i]){
int t=Mat[i][i]/Mat[j][i];
for(int k=i; k<n; ++k)
Mat[i][k]=(Mat[i][k]+Mod-1ll*Mat[j][k]*t%Mod)%Mod;
swap(Mat[i], Mat[j]), ret=-ret;
}
即,如果你主消第 j 行的话,可能因为常数问题而获得 52pts(可能得分有部分误差),此时建议你换成以下写法(主消第 i 行)
for(int j=i+1; j<n; ++j){
while(Mat[i][i]){
int t=Mat[j][i]/Mat[i][i];
for(int k=i; k<n; ++k)
Mat[j][k]=(Mat[j][k]+Mod-1ll*Mat[i][k]*t%Mod)%Mod;
swap(Mat[i], Mat[j]), ret=-ret;
}
swap(Mat[i], Mat[j]), ret=-ret;
}
初步估计可能是因为前者每一次开始消元的时候,面临的都是 Mat[i][j]=0,那么第一次消元将会是一次无效消元(因为 t=0),第一次消元的作用只有执行 swap() 这一个,消元部分没有执行。
并且,我在更改之后过掉了,发现我原本 TLE 的数据大多都跑了 1.14s,也即,我的超时是因为这些常数原因。
但是我真的不知道这种常数会有多大偏差,可能最多就是多个 2 ?但这样确实过不了。不过这样的卡常真的没有什么必要,每个人有自己的写法,这样真的没什么意义。如果有人是有目的地想要测试代码运行能力,他会自己关注自己的常数。
另,这种问题似乎不止我一个人在测试这道题时出现过了,同机房的国集爷也被卡了,昨天(指 20210721)也有一位同志出现同样的问题。本人也是在看那位同志的帖子时发现的这个问题,一测发现自己真是因为这个问题......十分无语= =.