A Matrix Equation
链接
https://ac.nowcoder.com/acm/contest/10662/A
题意
给你两个01方阵AB,你要找到一个01矩阵C,使得在2的模群中 ,其中 为一般矩阵乘积, 符号 为哈达马积(Hadamard product)
问你C有多少个解
数据范围
AB的行列都小于2000
题解
通过观察,我们发现C的每一列是互相独立的,不妨设他的第i列为 我们取出这里一列重新构建一个矩阵,这是一个n行一列的矩阵。 然后就有了 即 我们发现这是一个齐次线性方程组,直接使用高斯消元即可,时间复杂度 ,注意到是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; 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会检查序列,如果满足 , 符号 是二进制运算'或', Alice会对点 和点 连上一条无向边,最后Alice得到了一个图,他会检查这个图是否和他的树一摸一样,如果是,你就成功了。
数据范围
题解
考虑一个100个点的二分图,不妨假设这个二分图左侧的点比右侧的点少,且左侧的点的数量为x。则 。
我们给这 个点从0到 编号,最后为他们赋值 , 对于右边的点,我们假设他与编号在集合 的所有点相连,则我们为他赋值 , 由此方法,我们发现如果左边的点连向右边的点,他们的值的或恰好满足题意。
接下来我们要解决的是左侧的点与左侧的点不可连边,右侧的点与右侧的点不可连边,其实只需要让左侧和右侧的点的值分别以 开头即可。
然后树是一种特殊的二分图。此题已解决。
L Bit Sequence
链接
https://ac.nowcoder.com/acm/contest/10662/L
题意
定义函数 为 的二进制表示中,数字 出现的次数。
现在给你一个 串 ,问在区间 中有多少个 满足:
T组输入
数据范围
题解
分析 在 构成的序列 , 我们发现复制然后取反就能不断得到后面的值比如接下来的值就是 , 这个很好证明,其实本来是复制然后 ,但是在 的模群中, 其实就是取反。
然后就变成了在一个长度为 的字符串中寻找子串 出现的次数,由于 ,我们可以先分析长度恰好为128的母串A。然后翻转取反,分析接下来的长度为128的母串B,此后的所有串均为这AB排列得到,然后考虑跨越A或者跨越B的情况,由于 , , , ,所以跨越不会超过两个128长度的串所以我们直接对这四个情况分别统计即可,最后我们只能处理 的情况,对于剩下的一小部分,直接暴力即可。
时间复杂度