第45届ICPC亚洲赛区济南站

A Matrix Equation

链接

https://ac.nowcoder.com/acm/contest/10662/A

题意

给你两个01方阵AB,你要找到一个01矩阵C,使得在2的模群中A×C=BC ,其中 × 为一般矩阵乘积, 符号 哈达马积(Hadamard product)

问你C有多少个解

数据范围

AB的行列都小于2000

题解

通过观察,我们发现C的每一列是互相独立的,不妨设他的第i列为Ci 我们取出这里一列重新构建一个矩阵,这是一个n行一列的矩阵。 [C1iC2iC3i...Cni] 然后就有了 A×[C1iC2iC3i...Cni]=[B1iC1iB2iC2iB3iC3i...BniCni]=[B11B22B33Bni]×[C1iC2iC3i...Cni](A[B11B22B33Bni])×[C1iC2iC3i...Cni]=[000...0] 我们发现这是一个齐次线性方程组,直接使用高斯消元即可,时间复杂度O(N3),注意到是01矩阵,可以使用压位的方式降低64倍复杂度。

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
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <bitset>

using namespace std;


int getDel(vector<bitset<205>> a, int n) {
int row = 1;
for (int maxCol = 1; maxCol <= n; row++, maxCol++) {
if (a[row][maxCol] == 0) {
int i = row + 1;
while (i <= n && a[i][maxCol] == 0) {
i++;
}
if (i == n + 1) {
row--;
continue;
} else {
swap(a[i], a[row]);
}
}

for (int nextRow = row + 1; nextRow <= n; nextRow++) {
if (a[nextRow][maxCol] == 0) {
continue;
} else {
a[nextRow] ^= a[row];
}
}
}

return row - 1;
}


int main() {
ios::sync_with_stdio(false);
cin.tie(0);

const int mod = 998244353;

int n;
cin >> n;
vector<bitset<205>> a(n + 1), b(n + 1);

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int x;
cin >> x;
a[i][j] = x;
}
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int x;
cin >> x;
b[i][j] = x;
}
}

int pow[205] = {1};
for (int i = 1; i < 205; i++) {
pow[i] = int(pow[i - 1] * 2LL % mod);
}

int ans = 1;
for (int i = 1; i <= n; i++) {
vector<bitset<205>> t = a; // t = a - bi

for (int col = 1; col <= n; col++) {
t[col][col] = t[col][col] ^ b[col][i];
}

int del = getDel(t, n);
int tmp = pow[n - del];
ans = int(1LL * tmp * ans % mod);
}

cout << ans << endl;
}

J Tree Constructer

链接

https://ac.nowcoder.com/acm/contest/10662/J

题意

Alice有一颗树,你需要构造一个长度为n的序列,Alice会检查序列,如果满足ai|aj=2601, 符号|是二进制运算'或', Alice会对点i和点j连上一条无向边,最后Alice得到了一个图,他会检查这个图是否和他的树一摸一样,如果是,你就成功了。

数据范围

n<100,0<ai<260

题解

考虑一个100个点的二分图,不妨假设这个二分图左侧的点比右侧的点少,且左侧的点的数量为x。则x<50

我们给这x个点从0到x1编号,最后为他们赋值26012i(i), 对于右边的点,我们假设他与编号在集合S=s1,s2,s3...的所有点相连,则我们为他赋值2s1+2s2+2s3+..., 由此方法,我们发现如果左边的点连向右边的点,他们的值的或恰好满足题意。

接下来我们要解决的是左侧的点与左侧的点不可连边,右侧的点与右侧的点不可连边,其实只需要让左侧和右侧的点的值分别以01,10开头即可。

然后树是一种特殊的二分图。此题已解决。

L Bit Sequence

链接

https://ac.nowcoder.com/acm/contest/10662/L

题意

定义函数f(x)x的二进制表示中,数字1出现的次数。

现在给你一个01a,问在区间[0,L]中有多少个x满足: i[0,m1],f(x+i)mod2=ai

T组输入

数据范围

T<1000,|a|<100,L<1018

题解

分析f(x)x=0,1,2,3构成的序列0,1,1,0, 我们发现复制然后取反就能不断得到后面的值比如接下来的值就是1,0,0,1, 这个很好证明,其实本来是复制然后+1,但是在2的模群中,+1其实就是取反。

然后就变成了在一个长度为1018的字符串中寻找子串a出现的次数,由于|a|<100,我们可以先分析长度恰好为128的母串A。然后翻转取反,分析接下来的长度为128的母串B,此后的所有串均为这AB排列得到,然后考虑跨越A或者跨越B的情况,由于|AB|=256|AA|=256|BB|=256|BA|=256,所以跨越不会超过两个128长度的串所以我们直接对这四个情况分别统计即可,最后我们只能处理Lmod128=0的情况,对于剩下的一小部分,直接暴力即可。

时间复杂度O(T×256×4)