积和式模 4

首先,模 22 就是行列式的值。

我们考虑容斥,钦定某些列没有数被选,那么有

perm A=(1)nx{0,1}n(1)x1+x2++xni=1n(Ax)i\text{perm } A = (-1)^n \sum_{x \in \{0,1\}^n} (-1)^{x_1+x_2+\cdots +x_n} \prod _{i=1}^n (Ax)_i

也就是钦定某些列不选,然后每一行任意选一个数。

由于后面有一个 \prod ,也就是说一个 xx 会造成贡献当且仅当 AxAx00 的个数小于等于 11

于是我们考虑 AxAx 由于只有最多一个位置为 00 ,它只有 n+1n+1 种不同的值。所以我们可以枚举所有 AxAx 的取值,然后反解出所有 xx ,然后再代入 xx 求出值。

但是合法的 xx 的种类数可能很大,直接解这个东西复杂度是指数级的。

所以我们可以给这个矩阵加一行一列,得到:

(A1,1A1,2A1,nv1A2,1A2,2A2,nv2An,1An,2An,nvn00001)\left(\begin{array}{ccccc} A_{1,1} & A_{1,2} & \cdots & A_{1, n} & v_{1} \\ A_{2,1} & A_{2,2} & \cdots & A_{2, n} & v_{2} \\ \vdots & & & & \vdots \\ A_{n, 1} & A_{n, 2} & \cdots & A_{n, n} & v_{n} \\ 0 & 0 & 0 & 0 & 1 \end{array}\right)

显然这个矩阵的积和式等于原矩阵。

如果我们随机取一个向量 vv 整进去,那么对于一个确定的 AxAx ,每一组 xx 成为它的解的概率都是 12n\frac 1 {2^n} ,因为 vv 翻转一位一定会导致 xx 改变一位,而 vv 是随机选取的。又由于 xx 一共有 2n2^n 种,所以 AxAx 的解期望有 O(1)O(1) 个。

时间复杂度 O(n4)O(n^4)

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "ctime"
#include "queue"
#include "bitset"
using namespace std;
#define MAXN 306
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;

char ch[MAXN];
bitset<MAXN> A[MAXN] , a[MAXN];

int ok[MAXN];
int X[MAXN];

vi fre;
int re = 0;
void dfs( int s ) {
	if( s == fre.size() ) {
		per( i , n , 1 ) {
			int flg = 0 , ra = A[i][n + 1];
			rep( j , 1 , n ) if( A[i][j] ) {
				if( !flg ) flg = j;
				else 
					ra ^= X[j];
			}
			if( flg ) {
				X[flg] = ra;
			} else if( A[i][n + 1] ) return;
		}
		int tmp = 1 , sr = 0;
//		cout << A[2][3] << endl;
		rep( i , 1 , n ) {
			sr ^= X[i];
			int t = 0;
			rep( j , 1 , n ) if( X[j] ) 
				t = ( t + a[i][j] & 3 );
			tmp = tmp * t & 3;
		}
		tmp &= 3;
		if( sr ) tmp = 4 - tmp & 3;
		re += tmp;
	} else 
		rep( k , 0 , 1 ) X[fre[s]] = k , dfs( s + 1 );
}

int wkr( ) {
	rep( i , 1 , n ) A[i] = a[i];
	int cur = 1;
	rep( i , 1 , n ) {
		while( cur <= n ) {
			int flg = 0;
			rep( j , i , n ) if( A[j][cur] ) {
				if( i != j ) swap( A[j] , A[i] );
				flg = 1;
				break;
			}
			if( flg ) break;
			++ cur;
		}
		if( cur > n ) break;
		rep( j , i + 1 , n ) if( A[j][cur] ) A[j] ^= A[i];
		++ cur;
	}
	rep( i , 1 , n ) ok[i] = 0;
	rep( i , 1 , n ) {
		int flg = 0;
		rep( j , 1 , n ) if( A[i][j] ) { 
			ok[j] = 1; break;
		}
	}
	fre.clear();
	rep( i , 1 , n ) if( !ok[i] ) fre.pb( i );
	re = 0;
	dfs( 0 );
	return re;
}

void solve() {
	scanf("%d",&n);
	rep( i , 1 , n + 1 ) rep( j , 1 , n + 1 ) a[i][j] = A[i][j] = 0;
	rep( i , 1 , n ) {
		scanf("%s",ch + 1);
		rep( j , 1 , n ) a[i][j] = ch[j] - '0';
	} 
	rep( i , 1 , n ) a[i][n + 1] = rand() & 1;
	a[n + 1][n + 1] = 1;
	++ n;
//	rep( i , 1 , n ) {
//		rep( j , 1 , n ) printf("%d ",a[i].test(j)); puts("");
//	}
	rep( i , 1 , n ) a[i][n + 1] = 1;
	int res = 0;
	res += wkr( );
	rep( i , 1 , n ) {
		a[i][n + 1] = 0;
		res += wkr( );
		a[i][n + 1] = 1;
	}
	res %= 4;
	res = ( n & 1 ) ? 4 - res : res;
//	printf("%d\n",res % 4);
	puts( res % 4 ? "NO" : "YES" );
}

signed main() {
//	freopen("2.in","r",stdin);
	srand( time(0) );
    int T;cin >> T;while( T-- ) solve();
//    solve();
}

\