P2447 - 外星千足虫 题解

你们贪心你们的，我来讲一个动态高斯消元的小 trick。 首先容易想到二分，然后列异或方程组，`bitset` 优化对吧，复杂度 $\mathrm O\!\left(\dfrac{n^2m}w\log\right)$，过不去，把 $\log$ 去掉就能过了。 类似动态 dinic 那样，我们尝试把方程一个个添加进去，实时维护当前增广矩阵的简化阶梯型性，试图做到均摊总三方，也就是添加一次平方。然后每次就看秩有没有到 $n$，有的话就输出。 考虑把新的方程组添加到上一时刻的简化阶梯型的最下面，然后按普通步骤重新高斯消元。那么从左往右枚举主元列，当还没枚举到最后一行的时候，一定是前面的非零行并且行号递增，而且由于前面已经简化阶梯型了，要消主元位置所在列的其它非零元素是 $\mathrm O(1)$ 次的（只有新加行咯），从这点来说没有辜负我们对平方复杂度的期望。 然后到最后一行的主元的时候，就 swap 上来并且消一下该列其它非零元素，复杂度不用担心。然后后面不断有上面的跟最后一行换，当然这个对换变换复杂度也不用担心就是了，因朴素高消对换操作次数本来就缩水。而且之后上面非零行的消非零也都是 $\mathrm O(1)$ 次的，很满意。 适当简化一下过程，不想对换那么多次。那就先对上面的非零行消一下新加行的非零元素，然后反客为主，最后把新加行插入到适当的位置，不难证明这样做的正确性。由于是动态的，可以用 `vector<bitset>` 存矩阵，`insert` 函数用的很方便。代码很好写，1k 都不到，跑的也很快，孩子很喜欢。 ```cpp#include<bits/stdc++.h> using namespace std; const int N=1010; int n,m; vector<bitset<N> > a; int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ string str; cin>>str; bitset<N> nw; for(int j=1;j<=n;j++)nw[j]=str[j-1]^48; cin>>str; nw[n+1]=str[0]^48; for(int j=0;j<a.size();j++)if(a[j].any()){ int x=a[j]._Find_first(); if(nw[x])nw^=a[j]; } if(nw.any()){ int x=nw._Find_first(); for(int j=0;j<a.size();j++)if(a[j][x])a[j]^=nw; for(int j=0;j<=a.size();j++){ int y=j<a.size()&&a[j].any()?a[j]._Find_first():n+2; if(y>x){a.insert(a.begin()+j,nw);break;} } } // for(int j=0;j<a.size();j++)for(int k=1;k<=n+1;k++)cout<<a[j][k]<<" \n"[k==n+1]; if(a.size()==n){ cout<<i<<"\n"; for(int j=1;j<=n;j++)puts(a[j-1][n+1]?"?y7M#":"Earth"); return 0; } } puts("Cannot Determine"); return 0; } ```