高斯消元法
心情不好,来写博客...
思想
一种通过消元求解线性方程组的方法,时间复杂度为 \(n^3\)
和普通的消元法无二,选定一个自变量为主元,将一行的主元系数化为一,再通过乘法消去其他行含有该元的项。
实现细节
for(int j=0;j<n;j++){
int t;
for(t=curi;t<n;t++)
if(fabs(a[t][j])>eps)break;//对于浮点形的运算,一般定义小于一个常数就算是0了,这个常数视情况一般是1e-6
if(t==n)continue;//主元 not found,no sulution
for(int i=j;i<=n;i++)
swap(a[t][i],a[curi][i]);
for(int i=n;i>=j;i--)//这里要反着来,因为a[curi][j]的值还会用到
a[curi][i]/=a[curi][j];
for(int i=0;i<n;i++)
if(i!=curi)//本行不需要继续修改
for(int k=n;k>=j;k--)
a[i][k]-=a[curi][k]*a[i][j];//同样的原因
curi++;
}
拓展
容易发现,xor的运算也有同样的消元性质 \(a\oplus b \oplus b=a\)
因此可以利用高斯消元解异或方程组 模板题见外星千足虫。
异或方程组也就是
\(\begin{cases} a_{1,1}x_1 \operatorname{xor} a_{1,2}x_2\operatorname{xor}\cdots\operatorname{xor}a_{1,n}x_n &\equiv b_1 \pmod 2&&(1)\\ a_{2,1}x_1 \operatorname{xor} a_{2,2}x_2\operatorname{xor}\cdots\operatorname{xor}a_{2,n}x_n&\equiv b_2 \pmod 2&&(2)\\ \cdots&\cdots&&\cdots\\ a_{m,1}x_1 \operatorname{xor} a_{m,2}x_2\operatorname{xor}\cdots\operatorname{xor}a_{m,n}x_n&\equiv b_m \pmod 2&&(m) \end{cases}\)
for(int i=1;i<=n;i++){
now=i;
while(now<=m and !a[now][i])
now++;
if(now==m+1){
printf("Cannot Determine");
return 0;
}
ans=max(ans,now);
if(now!=i)
swap(a[now],a[i]);//怎么好像变简单了?因为异或的次数只有1和0,那么可以略过系数化为一这一步了
for(int j=1;j<=m;j++){
if(j==i)continue;
if(!a[j][i])continue;
a[j]^=a[i];
}
}
标签:xor,int,cdots,高斯消,operatorname,元法,curi
From: https://www.cnblogs.com/Hushizhi/p/17073089.html