当前位置: 代码迷 >> 综合 >> 【HDU - 4920】Matrix multiplication(矩阵乘法优化、bitset)
  详细解决方案

【HDU - 4920】Matrix multiplication(矩阵乘法优化、bitset)

热度:35   发布时间:2023-12-06 19:36:01.0

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;
}

 

  相关解决方案