样例中
1 -> 2,3 + 1(自身)
2 -> 1,3 + 2(自身)
3 -> 1,2 + 3(自身)
y总举的例子
1 -> 2 + 1(自身)
2 -> 1,3 + 2(自身)
3 -> 3(自身)
$x_{1}{~}x_{2}{~}x_{3}$ 分别表示3个开关有没有按
$$
\begin{align}
x_{1} \hat{} x_{2}=1 影响到1(右边)的有12(左边)\\\\
x_{1} \hat{} x_{2}=2 影响到2(右边)的有12(左边)\\\\
x_{2} \hat{} x_{2}=3 影响到3(右边)的有23(左边)
\end{align}
$$
$$
\begin{align}
1 {~} 1 {~} 0&=1 影响到1(右边)的有12(左边)\\\\
1 {~} 1 {~} 0&=1 影响到2(右边)的有12(左边)\\\\
0 {~} 1 {~} 1&=1 影响到3(右边)的有23(左边)\\\\
&=>\\\\
1 {~} 1 {~} 0&=1 \\\\
1 {~} 1 {~} 0&=1 \\\\
0 {~} 1 {~} 1&=1 \\\\
&=>(第二行减第一行)\\\\
1 {~} 1 {~} 0&=1 \\\\
0 {~} 0 {~} 0&=0 \\\\
0 {~} 1 {~} 1&=1 \\\\
&=>(第二行第三行互换)\\\\
1 {~} 1 {~} 0&=1 \\\\
0 {~} 1 {~} 1&=1 \\\\
0 {~} 0 {~} 0&=0 \\\\
\end{align}
$$
此时$x_{3}$无影响,可以任意取
取$x_{3}=0 则x_{2}=1 x_{1}=0$
取$x_{3}=1 则x_{2}=0 x_{1}=1$
结论:
当有k
=n-非零行个数
个自由变量
则每个自由变量有摁
和不摁
两种选法
所以答案数 = $2^{k}$
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 35;
int n;
int a[N][N];
int gauss()
{
int r,c;
for(r=1,c=1;c<=n;c++)
{
// 找主元
int t = r;
for(int i=r+1;i<=n;i++)
if(a[i][c])
t=i;
if(!a[t][c])continue;//不保证唯一解--不一定有主元
// 交换主元行至r行
for(int i=c;i<=n+1;i++)swap(a[t][i],a[r][i]);
// 用第r行的a[r][j]消第i行的a[i][j] 前提是第i行的最左边是1(有主元)
for(int i=r+1;i<=n;i++)
for(int j=n+1;j>=c;j--)
//等价于if(a[i][c]) a[i][j]^=a[r][j]
a[i][j] ^= a[i][c] & a[r][j];
//不能写a[i][j] ^= a[i][r] & a[r][j];
//是因为可能存在中间无主元的情况 此时r不++了 c还在循环中++ 导致r!=c
r++;
}
int res = 1;
//此时已经到了全零行
if (r < n + 1)
{
for (int i = r; i <= n; i ++ )
{
// 全零行的右边出现非零 无解
if (a[i][n + 1]) return -1; // 出现了 0 == !0,无解
res *= 2;
}
}
return res;
}
int main()
{
int T;
cin >> T;
while(T--)
{
memset(a,0,sizeof a);
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i][n+1];//初始状态
for(int i=1;i<=n;i++)
{
int t;
cin >> t;
a[i][n+1]^=t;//关心a[i][n+1](初始状态)和t(新状态)有没有发生变化
a[i][i]=1;//第i个开关一定会改变第i个灯
}
int x,y;
while(scanf("%d%d",&x,&y),x||y)
a[y][x]=1;
//第y个等式(行)的右边(开关y状态) 左边(操作开关x)(第x列)的系数=1
int t = gauss();
if (t == -1) puts("Oh,it's impossible~!!");
else printf("%d\n", t);
}
return 0;
}
老实人大哥的题解都是金品!