异或高斯消元。
考虑左半部分矩阵:令$a_{i,j}$表示$j$被按下时$i$是否会被影响。$x_i$表示是否按$i$
$$x_1a_{1,1}\ xor\ x_1a_{1,2}\ xor\ x_1a_{1,3}..xor\ x_1a_{1,n}=start_1\ xor\ end_1$$
$$(XOR_{j=1}^nx_ia_{i,j})=start_i\ xor\ end_i$$
实现时不需要建出矩阵,用状态压缩,将每一行压缩成一个整数。
消元时若出现$0=1$的方程则无解。否则,设自由元有$cnt$个,因为每个自由元取$0$或$1$,所以共有$2^{cnt}$组解。
时间复杂度$O(n^2)$
/**********/省略快读
#define MAXN 111
ll a[MAXN];
int main()
{
ll task=read();
while(task--)
{
ll n=read(),ans=1;
for(ll i=1;i<=n;++i)
{
ll cur=read();
a[i]=cur;
}
for(ll i=1;i<=n;++i)
{
ll cur=read();
a[i]^=cur;
a[i]|=(1<<i);
}
while(1)
{
ll x=read(),y=read();
if(!x&&!y)break;
a[y]|=(1<<x);//x影响y
}
for(ll i=1;i<=n;++i)
{
for(ll j=i+1;j<=n;++j)//找最高位最高的行
if(a[j]>a[i])std::swap(a[i],a[j]);
if(!a[i]){ans=1<<(n-i+1);break;}//0=0,消元完成,输出解的数量
if(a[i]==1){ans=0;break;}//0=1,无解
for(ll j=n;j;--j)
if(a[i]&(1<<j))
{
for(ll k=1;k<=n;++k)
if(i!=k&&(a[k]&(1<<j)))a[k]^=a[i];//消去
break;
}
}
if(ans)printf("%lld\n",ans);
else puts("Oh,it's impossible~!!");
}
return 0;
}
等式好像列错了,应该是xj,不是xi
为什么要枚举列然后枚举行呢,这样的操作如何同时进行消去和求解的呢,不是很清楚