这道题调了很久,发现由于取模运算,在优化版的高斯消元中,某种情况下会出现系数变为0的情况。记 gas[i][j] 表示第 i 个方程的第 j 个系数,有如下情况:
gas[1] = {1, 1000032, 1, ...};
gas[2] = {1000032, 1, 1, ...};
记 divs(x,y) 为模运算下除法,此时假如先解第二个未知数,则 ans[2] = divs(divs(1, 1000032) - 1, divs(1, 1000032) - 1000032)。假如先解第一个未知数,则 ans[1] = divs(1 - 1 * 1000032, 1 - 1000032 * 1000032)。两者由于取模运算,答案都为 0,同时基于解出的一个未知数,另一个未知数答案为 1。
可见,解方程组的顺序不同会导致答案不同。这道题我也错在了这里,先解最后一个未知数,就会错,先解第一个,就对了。为什么呢?