poj1830 开关问题[高斯消元]

其实第一反应是双向BFS或者meet in middle，$2^{14}$的搜索量，多测，应该是可以过的，但是无奈双向BFS我只写过一题，已经不会写了。

发现灯的操作情况顺序不影响结果，因为操作相当于在固定位进行xor运算，xor是可以随便交换的，所以顺序无所谓。

那么情况取决于每盏灯是否被操作过。设这个量为未知量$x_i$。于是可以设计方程，对于每个灯，有

$begin \text{xor} x_1 a_{1,1} \text{xor} x_2 a_{2,1} \text{xor} ... \text{xor} x_n a_{n,1} = end$

就是初始状态经过每一个灯对他的异或（这个异或是灯$i$是否操作乘上灯$i$是否影响这个灯，取$0/1$），最后得最终状态。

把$begin$初状态移到右边去。仿照高消内容，然后从第一个未知数开始消就行。

最后要问有多少种方案，也就是有多少个自由元可以随便取$0/1$，那答案就是$2^{自由元个数}$。否则全零系数的等式右边是$1$就无解。

感谢hkk上午给我讲无穷多解和无解的判断，不然我就要磕一下午了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define dbg(x) cerr << #x << " = " << x <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 int A[],bin[];

 int T,n,x,y,c,ans;

 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);

     for(register int i=;i<=;++i)bin[i]=<<i;

     read(T);while(T--){

         read(n);ans=;

         memset(A,,sizeof A);

         for(register int i=;i<=n;++i)read(x),A[i]|=x<<n;

         for(register int i=;i<=n;++i)read(x),A[i]^=x<<n;

         while(read(x),read(y))A[y]|=bin[x-];

         for(register int i=;i<=n;++i)A[i]|=bin[i-];

         for(x=,c=;c<=n;++c){//dbg(c),dbg(x),dbg(A[x]);

             for(y=x;y<=n&&!(bin[c-]&A[y]);++y);

             if(y==n+)continue;

             swap(A[x],A[y]);

             for(register int l=;l<=n;++l)if((l^x)&&(A[l]&bin[c-]))A[l]^=A[x];

             ++x;

         }

         for(register int i=x;i<=n;++i){

             if(A[i]&bin[n])ans=-;

             else ++ans;

         }

         if(ans<)puts("Oh,it's impossible~!!");

         else printf("%d\n",<<ans);

     }

     return ;

 }

Upd:这种题也可以用暴力枚举加小技巧优化来做，lyd书上在比较开头的地方有提到（“费解的开关”这题），复杂度$O(nm2^m)$。

巴特西

poj1830 开关问题[高斯消元]

最新文章

热门文章