莫欺少年穷，修魔之旅在这开始—>算法提高课题解

$a_{i{n+1}}\ (1\leqslant i\leqslant n)\ 应当是初始状态和目标状态的异或值$

$运用高斯消元求解异或方程组即可$

$假设自由元为\ k，则方案数为\ 2^k$

#include<bits/stdc++.h>

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;

        for(int i=c;i<=n+1;i++) swap(a[t][i],a[r][i]);

        for(int i=r+1;i<=n;i++)
            for(int j=n+1;j>=c;j--)
                a[i][j]^=a[i][c]&a[r][j];

        r++;
    }

    int res=1;
    if(r<=n)
        for(int i=r;i<=n;i++) 
            if(a[i][n+1]) return -1; //无解
            else 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][i]=1; //自己控制自己
        }

        int x,y;
        while(cin>>x>>y,x||y) a[y][x]=1; // 第 y 盏灯由第 x 个开关控制

        int res=gauss();
        if(res==-1) puts("Oh,it's impossible~!!");
        else cout<<res<<endl;
    }

    return 0;
}