与51nod1140一样。不过这题是多组数据的。。。坑。。。。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<ctime>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}
const int nmax=1005;
ll r[nmax],ra[nmax],rb[nmax],rc[nmax],a[nmax][nmax],b[nmax][nmax],c[nmax][nmax];
int main(){
srand(1000007);
int n;bool flag;
while(scanf("%d",&n)==1){
rep(i,1,n) rep(j,1,n) a[i][j]=read();
rep(i,1,n) rep(j,1,n) b[i][j]=read();
rep(i,1,n) rep(j,1,n) c[i][j]=read();
rep(i,1,n) r[i]=rand()%1000,ra[i]=rb[i]=rc[i]=0;
rep(j,1,n) rep(k,1,n) ra[j]+=r[k]*a[k][j];
rep(j,1,n) rep(k,1,n) rb[j]+=ra[k]*b[k][j];
rep(j,1,n) rep(k,1,n) rc[j]+=r[k]*c[k][j];
flag=1;
rep(i,1,n) if(rc[i]!=rb[i]){
printf("No\n");flag=0;
}
if(flag) printf("Yes\n");
}
return 0;
}
2396: 神奇的矩阵
Time Limit: 5 Sec Memory Limit: 512 MB
Submit:
1042 Solved: 298
[Submit][Status][Discuss]
Description
给出三个行数和列数均为N的矩阵A、B、C,判断A*B=C是否成立。
Input
题目可能包含若干组数据。
对于每组数据,第一行一个数N,接下来给出三个N*N的矩阵,依次为A、B、C三个矩阵。
Output
对于每组数据,若A*B=C成立,则输出Yes,否则No。每个答案占一行。
Sample Input
2
2
100
Sample Output
HINT
对于90%的数据,N不超过100;
对于100%的数据,N不超过1000,矩阵中的数字大于等于0小于1000,数据组数不超过5组。
Source
bzoj2396: 神奇的矩阵的更多相关文章
-
BZOJ2396 神奇的矩阵 【随机化 + 矩乘】
题目链接 BZOJ2396 题解 一种快速判断两个矩阵是否相等的方法: 对于两个\(n * n\)矩阵,两边同时乘一个\(n * 1\)的随机矩阵,如果结果相等,那么有很大概率两个矩阵相等 如果左边是 ...
-
bzoj2396: 神奇的矩阵(矩阵乘法+随机化)
这题n三方显然会GG... 运用矩阵乘法的性质A*B*R=A*(B*R)=C*R,于是随机化出一个一列的R,就可以把复杂度降低成n方...大概率是不会错的 #include<iostream&g ...
-
bzoj2396 神奇的矩阵(随机化)
Time Limit: 5 Sec Memory Limit: 512 MB 给出三个行数和列数均为N的矩阵A.B.C,判断A*B=C是否成立. 题目可能包含若干组数据. 对于每组数据,第一行 ...
-
[Swust OJ 1126]--神奇的矩阵(BFS,预处理,打表)
题目链接:http://acm.swust.edu.cn/problem/1126/ Time limit(ms): 1000 Memory limit(kb): 65535 上一周里,患有XX症的哈 ...
-
神奇的矩阵 NOI模拟题
神奇的矩阵 题目大意 有一个矩阵\(A\),第一行是给出的,接下来第\(x\)行,第\(y\)个元素的值为数字\(A_{x-1,y}\)在\(\{A_{x-1,1},A_{x-1,2},A_{x-1, ...
-
【bzoj2396】神奇的矩阵 随机化
题目描述 给出三个行数和列数均为N的矩阵A.B.C,判断A*B=C是否成立. 输入 题目可能包含若干组数据.对于每组数据,第一行一个数N,接下来给出三个N*N的矩阵,依次为A.B.C三个矩阵. 输出 ...
-
[XJOI NOI2015模拟题13] A 神奇的矩阵 【分块】
题目链接:XJOI NOI2015-13 A 题目分析 首先,题目定义的这种矩阵有一个神奇的性质,第 4 行与第 2 行相同,于是第 5 行也就与第 3 行相同,后面的也是一样. 因此矩阵可以看做只有 ...
-
D.Starry的神奇魔法(矩阵快速幂)
/*D: Starry的神奇魔法 Time Limit: 1 s Memory Limit: 128 MB Submit My Status Problem Description ...
-
神奇的矩阵(bzoj 2396)
Description 给出三个行数和列数均为N的矩阵A.B.C,判断A*B=C是否成立. Input 题目可能包含若干组数据. 对于每组数据,第一行一个数N,接下来给出三个N*N的矩阵,依次为 ...
随机推荐
-
PHP基础知识之字符串运算符
两个字符串相加用 . 运算符(类似于+),如$a="str1" . "str2";$b=$a . "str3";=>"str ...
-
自制Unity小游戏TankHero-2D(4)关卡+小地图图标+碰撞条件分析
自制Unity小游戏TankHero-2D(4)关卡+小地图图标+碰撞条件分析 我在做这样一个坦克游戏,是仿照(http://game.kid.qq.com/a/20140221/028931.htm ...
-
判断滑动方向UITableView
CGFloat lastContentOffset; //ScoreView 滑动位置 -(void)scrollViewWillBeginDragging:(UIScrollView*)scrol ...
-
Linux学习笔记28——消息队列
一 关于消息队列 消息队列提供了一种从一个进程向另一个进程发送一个数据块的方法,而且,每个数据块都被认为含有一个类型,接收进程可以独立地接受含有不同类型值的数据块.可以通过发送消息来几乎完全避免命名管 ...
-
Eclipse下生成/编辑Java类图或时序图(UML)[转载]
一 引用文章 1.[eclipse下生成Java类图和时序图,生成UML图(更完整版)](https://blog.csdn.net/guomainet309/article/details/5302 ...
-
Python3-操作系统发展史
操作系统发展史 手工操作 —— 穿孔卡片 批处理 —— 磁带存储 多道程序系统 操作系统的作用 手工操作 —— 穿孔卡片 1946年第一台计算机诞生--20世纪50年代中期,计算机工作还在采用手工操作 ...
-
[UWP]缓存Lottie动画帧
在上一篇博文<[UWP]在UWP平台中使用Lottie动画>中我简单介绍了一下LottieUWP项目以及如何使用它呈现Lottie动画,这篇文章里我们来讲点进阶的东西--缓存Lottie动 ...
-
关于JSON 与 对象 、集合 之间的转换
在开发过程中,经常需要和别的系统交换数据,数据交换的格式有XML.JSON等,JSON作为一个轻量级的数据格式比xml效率要高,XML需要很多的标签,这无疑占据了网络流量,JSON在这方面则做的很好, ...
-
用户 &#39;IIS APPPOOL\DefaultAppPool&#39; 登录失败【收藏】
转载:http://blog.csdn.net/wenjie315130552/article/details/7246143 问题是应用程序连接池的问题.网上有些朋友说是Temp文件夹的权限的问题. ...
-
es 中的 Set 和 Map
Set 函数可以接受一个数组(或者具有 iterable 接口的其他数据结构)作为参数,用来初始化.