• 如果喜欢本站,您可以按CTRL+D收藏本站,方便下次访问。

  • 欢迎来自五湖四海的朋友,期待为您分享有价值的资源 :oops:

POJ 3318 Matrix Multiplication 随机化算法

POJ解题 第四度 10年前 (2010-08-27) 61次浏览 0个评论 扫描二维码

file

Matrix Multiplication

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 11924 Accepted: 2408

Description

You are given three n × n matrices A, B and C. Does the equation A × B = C hold true?

Input

The first line of input contains a positive integer n (n ≤ 500) followed by the the three matrices A, B and C respectively. Each matrix\\’s description is a block of n × n integers.

It guarantees that the elements of A and B are less than 100 in absolute value and elements of C are less than 10,000,000 in absolute value.

Output

Output YES if the equation holds true, otherwise NO.

Sample Input

<pre class="sio">2
1 0
2 3
5 1
0 8
5 1
10 26

Sample Output

<pre class="sio">YES

Hint

Multiple inputs will be tested. So O(n3) algorithm will get TLE.

Source

给定矩阵A和B,判断矩阵C是不是它们的乘积。

题目明确表示直接判断会超时,而Strass和直接相乘的O(n^3)效果相差不多。 因而采用随机化方法,按我自己的想法,随机测试C中的若干元素,以确定结果,看了讨论区,才发现有更加“专业”的办法。 随机生成行向量I,则若AB=C,那么必有IAB=IC;反之,不一定成立,算法的随机性正体现在这里。 用一个必要不充分条件来判断结果的正确性,比盲目测试效果往往要好得多。 这个必要条件判断结果的时间复杂度是O(N^2)的,这是题目输入数据量可以接受的。

/*Source Code

Problem: 3318  User: y09
Memory: 3080K  Time: 1063MS
Language: C  Result: Accepted

Source Code */
#include <stdio.h>
#include <time.h>
#include<stdlib.h>
int main()
{
    int n;
    int i,j;
    int mat1[500][500];
    int mat2[500][500];
    int mat3[500][500];
    __int64 te1[500]={0};
    __int64 te2[500]={0};
    __int64 te3[500]={0};
    __int64 te4[500]={0};
    time_t t;
    srand((unsigned) time(&t));
    scanf(“%d“,&n);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf(“%d“,&mat1[i][j]);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf(“%d“,&mat2[i][j]);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf(“%d“,&mat3[i][j]);
    for(i=0;i<n;i++)
        te1[i]=rand()%100;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            te2[i]+=te1[j]*mat1[j][i];
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            te3[i]+=te2[j]*mat2[j][i];
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            te4[i]+=te1[j]*mat3[j][i];
    for(i=0;i<n;i++)
        if(te3[i]!=te4[i])
        {
            puts(“NO“);
            return 0;
        }
    puts(“YES“);

    return 0;
}

本网站采用BY-NC-SA 4.0协议进行授权 | 转载请注明原文链接:https://www.disidu.com/post/1016.html
如果觉得本文对您有帮助或者您心情好~可以微信打赏支持一下本站:↓↓↓
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址