积和式模 4

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

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

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

由于后面有一个 $\prod$ ,也就是说一个 $x$ 会造成贡献当且仅当 $Ax$ 中 $0$ 的个数小于等于 $1$ 。

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

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

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

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

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

时间复杂度 $O(n^4)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#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();
}

文章作者: yijan
文章链接: https://yijan.co/2021/04/20/ji-he-shi-mo-dollar4dollar/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog