警醒后人 + 一点牢骚
查看原帖
警醒后人 + 一点牢骚
125355
Mihari楼主2021/7/21 22:02

注意,本题如果你使用的类似辗转相除法原理的消元,那么这种写法可能会导致你的部分 TLE\rm 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;
}

即,如果你主消第 jj 行的话,可能因为常数问题而获得 52pts52pts(可能得分有部分误差),此时建议你换成以下写法(主消第 ii 行)

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\tt Mat[i][j]=0,那么第一次消元将会是一次无效消元(因为 t=0t=0),第一次消元的作用只有执行 swap()\tt swap() 这一个,消元部分没有执行。

并且,我在更改之后过掉了,发现我原本 TLE\rm TLE 的数据大多都跑了 1.14s1.14s,也即,我的超时是因为这些常数原因。

但是我真的不知道这种常数会有多大偏差,可能最多就是多个 22 ?但这样确实过不了。不过这样的卡常真的没有什么必要,每个人有自己的写法,这样真的没什么意义。如果有人是有目的地想要测试代码运行能力,他会自己关注自己的常数。

另,这种问题似乎不止我一个人在测试这道题时出现过了,同机房的国集爷也被卡了,昨天(指 2021072120210721)也有一位同志出现同样的问题。本人也是在看那位同志的帖子时发现的这个问题,一测发现自己真是因为这个问题......十分无语= =.

2021/7/21 22:02
加载中...