首页 > 代码库 > hdu 4920 Matrix multiplication bitset优化常数
hdu 4920 Matrix multiplication bitset优化常数
Matrix multiplication
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Problem Description
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.
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 Aij. The next n lines describe the matrix B in similar format (0≤Aij,Bij≤109).
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 Aij. The next n lines describe the matrix B in similar format (0≤Aij,Bij≤109).
Output
For each tests:
Print n lines. Each of them contain n integers -- the matrix A×B in similar format.
Print n lines. Each of them contain n integers -- the matrix A×B in similar format.
Sample Input
10120 12 34 56 7
Sample Output
00 12 1
Author
Xiaoxu Guo (ftiasch)
Source
2014 Multi-University Training Contest 5
题意:给你两个矩阵,求矩阵相乘%3;
思路:正常思路n*n*n求解(运气好可以ac。。。),看了下数据范围由于mod=3,所以利用bitset标记每行1,2,0的位置,取并集就可以得到相同位置的个数;
这样就可以优化最后的一个n。详见代码;
#include<bits/stdc++.h>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14const int N=1e3+10,M=1e6+10,inf=1e9+10;const ll INF=1e18+10,mod=2147493647;int n;bitset<N>a[N][5],b[N][5];int ans(int i,int j){ int u=(a[i][1]&b[j][1]).count(),v=(a[i][1]&b[j][2]).count(); int x=(a[i][2]&b[j][1]).count(),y=(b[j][2]&a[i][2]).count(); return u+v*2+x*2+y*4;}int main(){ 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(); for(int i=0; i<n; i++) for(int j=0; j<n; j++) { int x; scanf("%d",&x); a[i][x%3].set(j); } for(int i=0; i<n; i++) for(int j=0; j<n; j++) { int x; scanf("%d",&x); b[j][x%3].set(i); } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) printf("%d%c",ans(i,j)%3,(j!=n-1?‘ ‘:‘\n‘)); } } return 0;}
hdu 4920 Matrix multiplication bitset优化常数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。