求矩阵A和B相乘的结果。
因为答案只要对3取模，所以我们可以通过一些方法来加速计算。
我们对两个矩阵各开两个bitset，分别存储模3余1和模3余2的数。
然后相乘的时候and一下就好了。
c[i][j] = f(a_one[i] & b_one[j]) + f(a_one[i] & b_two[j]) * 2 + f(a_two[i] & b_one[j]) * 2 + f(a_two[i] & b_two[j])
$f(x)$表示 x中1的个数
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; const int A = 810;
const int mod = 3; int n;
bitset <A> a_one[A], a_two[A], b_one[A], b_two[A], tmp;
int x; int main(){ while (~scanf("%d", &n)){ rep(i, 1, n){
a_one[i].reset();
a_two[i].reset();
b_one[i].reset();
b_two[i].reset();
} rep(i, 1, n){
rep(j, 1, n){
scanf("%d", &x);
x %= 3;
if (x == 1) a_one[i].set(j);
else if (x == 2) a_two[i].set(j);
}
} rep(i, 1, n){
rep(j, 1, n){
scanf("%d", &x);
x %= 3;
if (x == 1) b_one[j].set(i);
else if (x == 2) b_two[j].set(i);
}
} rep(i, 1, n){
rep(j, 1, n){
int ans = 0;
tmp = a_one[i] & b_one[j];
ans += tmp.count();
tmp = a_one[i] & b_two[j];
ans += 2 * tmp.count();
tmp = a_two[i] & b_one[j];
ans += 2 * tmp.count();
tmp = a_two[i] & b_two[j];
ans += tmp.count();
ans %= 3;
printf("%d", ans);
if (j < n) putchar(32);
}
putchar(10);
} } return 0;
}