首页 > 代码库 > hdu4920 Matrix multiplication 模3矩阵乘法
hdu4920 Matrix multiplication 模3矩阵乘法
hdu4920
Matrix multiplicationTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 568 Accepted Submission(s): 225Problem 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. 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). Output For each tests: 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 Recommend We have carefully selected several similar problems for you: 4919 4918 4917 4916 4914 |
2014多校5的最水的题,我没做出来,怕了。
题意:给出两个n*n的矩阵A和B,求A*B结果矩阵,元素都模3,n<=800。
题解:矩阵乘法加剪枝(?)。
800*800的矩阵,多组数据,直接算是会超时得飞起来的,只有考虑模3的特殊性。
读入后每个元素模3,得到的矩阵里全是0,1,2,随机数据的话有三分之一是零,所以我们的矩阵乘法要用k i j的循环嵌套顺序,第二层里面发现A[i][k]==0时就continue,直接少一维,也就是1/3概率少一维。这个是这题最关键的一步,没想到这步的话,其他再怎么优化也没用(我们试过了……)。
另外运算时可以使用cal[i][j][k]提前计算好((i*j)+k)%3,矩阵乘法的时候直接用这个结果。
------------------------------其他------------------------------------
顺便说个笑话:为什么Dijkstra没发明Floyd算法?因为他是ijk不是kij……
比赛的时候我们做这题优化得飞起来,读入输出优化,gets按字符串读一行来处理,输出用putchar,乘法、取余运算用上面说的那步省掉,输出不用‘0‘+C[i][j]而用数组存好ch[0]=‘0‘这样输出,就差用fread一次读多行了……可是就是TLE,因为我们没想到最关键那步……
代码:
1 #pragma comment(linker, "/STACK:102400000,102400000") 2 3 #include<cstdio> 4 #include<cmath> 5 #include<iostream> 6 #include<cstring> 7 #include<algorithm> 8 #include<cmath> 9 #include<map>10 #include<set>11 #include<stack>12 #include<queue>13 using namespace std;14 #define ll __int6415 #define usint unsigned int16 #define mz(array) memset(array, 0, sizeof(array))17 #define minf(array) memset(array, 0x3f, sizeof(array))18 #define REP(i,n) for(int i=0;i<(n);i++)19 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)20 #define RD(x) scanf("%d",&x)21 #define RD2(x,y) scanf("%d%d",&x,&y)22 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)23 #define WN(x) printf("%d\n",x);24 #define RE freopen("D.in","r",stdin)25 #define WE freopen("1.out","w",stdout)26 int n;27 28 const int maxn=800;29 int A[maxn][maxn],B[maxn][maxn],C[maxn][maxn];30 int cal[3][3][3];31 int main() {32 int i,j,k;33 for(i=0; i<3; i++)34 for(j=0; j<3; j++)35 for(k=0; k<3; k++)36 cal[i][j][k]=((i*j)+k)%3;37 while(scanf("%d",&n)!=EOF) {38 for(i=0; i<n; i++)39 for(j=0; j<n; j++) {40 scanf("%d",&A[i][j]);41 A[i][j]%=3;42 }43 for(i=0; i<n; i++)44 for(j=0; j<n; j++) {45 scanf("%d",&B[i][j]);46 B[i][j]%=3;47 }48 mz(C);49 for(k=0; k<n; k++)50 for(i=0; i<n; i++) {51 if(A[i][k]==0)continue;///这个是关键!模3有三分之一是零,也就有三分之一概率去一维,碉!52 for(j=0; j<n; j++) {53 ///re.a[i][j]=(re.a[i][j]+(A.a[i][k]*B.a[k][j]));54 C[i][j]=cal[A[i][k]][B[k][j]][C[i][j]];55 }56 }57 for(i=0; i<n; i++) {58 for(j=0; j<n-1; j++) {59 putchar(C[i][j]+‘0‘);60 putchar(‘ ‘);61 }62 putchar(C[i][n-1]+‘0‘);63 puts("");64 }65 }66 return 0;67 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。