Given two matrices A and B of size n×n, find the product of them.
bobo hates big integers. So you are only asked to find the result modulo 3.
Input
The input consists of several tests. For each tests:
The first line contains n (1≤n≤800). Each of the following n lines contain n integers -- the description of the matrix A. The j-th integer in the i-th line equals A ij. The next n lines describe the matrix B in similar format (0≤A ij,Bij≤10 9).
Output
For each tests:
Print n lines. Each of them contain n integers -- the matrix A×B in similar format.
Sample Input
1 0 1 2 0 1 2 3 4 5 6 7
Sample Output
0 0 1 2 1
题意：
矩阵乘法+取余。
思路：
以前一直没注意过这种写法，现在才知道先枚举k在枚举j速度会快一些。另外的方法就是使用bitset，开两个bitset，一个a，一个b。a[i][j]代表第i行存j这个数的状况，状况就是如果这个位上存着j那么a[i][j]里面这个位上的数是1，否则是0。b的第一维代表着列即第一行存着的是第一列的信息，b[i][j]代表第i列存j这个数的状况，因为在矩阵乘法时第一个矩阵一次需要看一行，第二个数组一次需要看一列。求结果分四种情况，看看a中第i行和b中第j列相同位置为1的位置的数量，再乘上权值。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
#include<bitset>
#define MOD (1000000000+7)
using namespace std;
typedef long long ll;
int a[810][810],b[810][810],ans[810][810];
int main()
{int n;while(~scanf("%d",&n)){for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&a[i][j]),a[i][j]%=3,ans[i][j]=0;;for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&b[i][j]),b[i][j]%=3;for(int i=0;i<n;i++)for(int k=0;k<n;k++)for(int j=0;j<n;j++)ans[i][j]=(ans[i][j]+a[i][k]*b[k][j])%3;for(int i=0;i<n;i++){printf("%d",ans[i][0]);for(int j=1;j<n;j++)printf(" %d",ans[i][j]);puts("");}}return 0;
}#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
#include<bitset>
#define MOD (1000000000+7)
using namespace std;
typedef long long ll;
bitset<1000> a[810][3],b[810][3];
int main()
{int n;while(~scanf("%d",&n)){for(int i=0;i<n;i++)for(int j=0;j<3;j++){a[i][j].reset();b[i][j].reset();}int d;for(int i=0;i<n;i++)for(int j=0;j<n;j++){scanf("%d",&d);a[i][d%3].set(j);}for(int i=0;i<n;i++)for(int j=0;j<n;j++){//列倒着存的，b[j][k],代表第j列，里面存的元素为k时，哪些元素是 scanf("%d",&d);b[j][d%3].set(i);}//bitset 第一行两个位置都为1的数的个数，行为1列为2或者行2列1的个数，行列都为2的个数 for(int i=0;i<n;i++){for(int j=0;j<n;j++){d=((a[i][1]&b[j][1]).count()+(a[i][1]&b[j][2]).count()*2+(a[i][2]&b[j][1]).count()*2+(a[i][2]&b[j][2]).count())%3; if(j==n-1) printf("%d\n",d);else printf("%d ",d);}}}return 0;
}