前置知识
解法
把开关的相互影响关系转化成异或,然后就转化成了异或方程组,高斯消元求解即可。
判断是否存在解的过程同 luogu P2455 [SDOI2006] 线性方程组 。
由于自由元仅能取 \(0/1\),故总方案数为 \(2\) 的自由元数量次方。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
int start[50],en[50],a[50][50];
int main()
{
int t,n,i,j,k,l,r,ii,h,val,ans;
cin>>t;
for(h=1;h<=t;h++)
{
cin>>n;
ans=0;
memset(a,0,sizeof(a));
for(i=1;i<=n;i++)
{
cin>>start[i];
}
for(i=1;i<=n;i++)
{
cin>>en[i];
a[i][i]=1;
a[i][n+1]=start[i]^en[i];
}
while(cin>>l>>r)
{
if(l==0&&r==0)
{
break;
}
else
{
a[r][l]=1;
}
}
for(i=1;i<=n;i++)
{
val=i;
for(j=1;j<=n;j++)
{
if(!(i>j&&a[j][j]!=0))
{
if(a[j][i]>a[val][i])
{
val=j;
}
}
}
for(j=1;j<=n+1;j++)
{
swap(a[i][j],a[val][j]);
}
for(j=1;j<=n;j++)
{
if(j!=i&&a[j][i]==1)
{
for(k=i+1;k<=n+1;k++)
{
a[j][k]^=a[i][k];
}
}
}
}
for(i=1;i<=n;i++)
{
if(a[i][i]==0)
{
if(a[i][n+1]!=0)
{
ans=-1;
break;
}
else
{
ans++;
}
}
}
if(ans==-1)
{
cout<<"Oh,it's impossible~!!"<<endl;
}
else
{
cout<<(1<<ans)<<endl;
}
}
return 0;
}
标签:en,P10499,val,题解,50,long,开关,异或,define
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18238537