HDU 4920 Matrix multiplication(矩阵相乘)

HDU 4920 Matrix multiplication(矩阵相乘)

大家好,又见面了,我是全栈君。

各种TEL,233啊。没想到是处理掉0的情况就能够过啊。一直以为会有极端数据。没想到居然是这种啊、、在网上看到了一个AC的奇妙的代码,经典的矩阵乘法,仅仅只是把最内层的枚举,移到外面就过了啊、、、有点不理解啊,复杂度不是一样的吗、、

Matrix multiplication

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 640    Accepted Submission(s): 250




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.

 


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,B
ij≤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

 


Author
Xiaoxu Guo (ftiasch)
 


Source
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-12
///#define M 1000100
#define LL __int64
///#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?

0:x)using namespace std;const int maxn = 810;int a[maxn][maxn];int b[maxn][maxn];int c[maxn][maxn];int aa[maxn][maxn];int bb[maxn][maxn];int main(){ int n; while(cin >>n) { memset(c, 0, sizeof(c)); memset(aa, 0, sizeof(aa)); memset(bb, 0, sizeof(bb)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { scanf("%d",&a[i][j]); a[i][j] %= 3; } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { scanf("%d",&b[i][j]); b[i][j] %= 3; } } for(int i = 1; i <= n; i++) { int x = -1; for(int j = n; j >= 0; j--) { aa[i][j] = x; if(a[i][j]) x = j; } } for(int i = 1; i <= n; i++) { int x = -1; for(int j = n; j >= 0; j--) { bb[i][j] = x; if(b[i][j]) x = j; } } for (int i = 1; i <= n; i++) { for(int j = aa[i][0]; j != -1; j = aa[i][j]) { for(int k = bb[j][0]; k != -1; k = bb[j][k]) c[i][k] += a[i][j]*b[j][k]; } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n-1; j++) printf("%d ",c[i][j]%3); printf("%d\n",c[i][n]%3); } } return 0;}

这是看到有人交的AC的代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 805;
int a[N][N], b[N][N], ans[N][N];
int main()
{
    int n, i, j, k;
    while(~scanf("%d",&n))
    {
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
            {
                scanf("%d",&a[i][j]);
                a[i][j] %= 3;
            }
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
            {
                scanf("%d",&b[i][j]);
                b[i][j] %= 3;
            }
        memset(ans, 0, sizeof(ans));
        for(k = 1; k <= n; k++) //经典算法中这层循环在最内层。放最内层会超时,可是放在最外层或者中间都不会超时,不知道为什么
            for(i = 1; i <= n; i++)
                for(j = 1; j <= n; j++)
                {
                    ans[i][j] += a[i][k] * b[k][j];
                    //ans[i][j] %= 3;   //假设在这里对3取余,就超时了
                }
        for(i = 1; i <= n; i++)
        {
            for(j = 1; j < n; j++)
                printf("%d ", ans[i][j] % 3);
            printf("%d\n", ans[i][n] % 3);
        }
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115239.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • SplitContainer控件设置固定比例

    SplitContainer控件设置固定比例SplitContainer控件2个panel如何设置均等大小.(竖直拆分)先随意设置空间高的大小,然后如果想要均等显示,则直接设置SplitterDistance为高的一半,即可!随后任意改变控件大小,都不会改变均等显示比例。同理3:7,4:6…

  • Dreamweaver8的安装

    Dreamweaver8的安装安装步骤:Step1:双击<Dreamweaver8-chs>Step2:单击<下一步>Step3:选中<我接受该许可证协议中的条款>,单击<下一步>按钮Step4:选中<在桌面上创建快捷方式(针对所有用户)>,单击<下一步>Step5:单击<下一步>S…

  • C#一个方法返回多个值建议收藏

    示例代码:1staticvoidMain(string[]args)2{3//声明4intvalue;5stringstrOutValue;67//调用函数8/

    2021年12月21日
  • copy.deepcopy()_python 内存管理

    copy.deepcopy()_python 内存管理参考文章http://iaman.actor/blog/2016/04/17/copy-in-python**首先直接上结论:—–我们寻常意义的复制就是深复制,即将被复制对象完全再复制一遍作为独立的新个体单独存在。所以改变原有被复制对象不会对已经复制出来的新对象产生影响。—–而浅复制并不会产生一个独立的对象单独存在,他只是将原有的数据块打上一个新标签,所以当其中一个标签被…

  • 微信小程序搭建测试环境_微信小程序 视频

    微信小程序搭建测试环境_微信小程序 视频开发环境:一、概念二、开发环境的组成三、配置基本流程及流程总结:测试环境:一、概述:测试环境的秩序体现在以下几个环节:生产环境(线上环境):一、概述:二、上线原则总结

    2022年10月28日
  • PIC 指令周期_三菱plc分钟计时指令

    PIC 指令周期_三菱plc分钟计时指令一、PIC指令周期计算:设工作频率为:F(MHz);1个指令周期为1/(F/4)秒。二、PIC的指令 即汇编指令,不同系列指令数不一样。  8位单片机共有三个级别,有相对应的指令集。基本级PIC系列芯片共有指令33条,每条指令是12位字长;中级PIC系列芯片共有指令35条,每条指令是14位字长;高级PIC系列芯片共有指令58条,每条指令是16位字长。其指令向下兼容

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号