[luoguP2447] [SDOI2010]外星千足虫（高斯消元 + bitset）

传送门

用bitset优化，要不然n^3肯定超时

消元过程中有几点需要注意，找到最大元后break，保证题目中所说的K最小

如果有自由元说明解很多，直接返回

#include <bitset> #include <cstdio> #define N 2050 #define max(x, y) ((x) > (y) ? (x) : (y)) int n, m, ans; std::bitset <N> s[N]; char S[N][N]; inline int read() inline bool Gauss() if(!s[k][j]) return 0; if(k != j) swap(s[k], s[j]); for(i = j + 1; i <= m; i++) if(s[i][j]) s[i] ^= s[j]; } for(i = n; i >= 1; i) for(j = i + 1; j <= n; j++) s[i][n + 1] = s[i][n + 1] ^ (s[i][j] * s[j][n + 1]); } int main() if(Gauss()) else puts("Cannot Determine"); return 0; }

　　

上一篇：[luoguP1627] 中位数（模拟？）

下一篇：[luoguP2129] L国的战斗续之多路出击（模拟 || 矩阵）

---

高斯消元 bitset