【bzoj2396】神奇的矩阵 随机化
2024-09-29 03:09:04
题目描述
给出三个行数和列数均为N的矩阵A、B、C,判断A*B=C是否成立。
输入
题目可能包含若干组数据。
对于每组数据,第一行一个数N,接下来给出三个N*N的矩阵,依次为A、B、C三个矩阵。
输出
对于每组数据,若A*B=C成立,则输出Yes,否则No。每个答案占一行。
样例输入
1
2
2
100
样例输出
No
题解
随机化
如果直接把$A$与$B$的乘积算出来肯定会GG。。
考虑,如果$A*B=C$,那么$T*(A*B)=T*C$,而矩阵乘法具有结合律,因此有$(T*A)*B=T*C$。如果取$T$为$1*n$的行向量,那么每一步矩阵乘法的复杂度都是$O(n^2)$的。
于是可以使用这种方法大致判断出$A*B$是否等于$C$。随机出$T$矩阵,然后判断$(T*A)*B$与$T*C$是否相等即可。大约每组数据随机10次即可出解。
#include <cstdio>
#include <algorithm>
#define N 1010
using namespace std;
typedef long long ll;
ll a[N][N] , b[N][N] , c[N][N] , t[N] , v[N];
bool judge(int n)
{
int cnt , i , j;
ll sb , sc;
for(cnt = 1 ; cnt <= 10 ; cnt ++ )
{
for(i = 1 ; i <= n ; i ++ ) t[i] = rand() % 999 + 1;
for(i = 1 ; i <= n ; i ++ )
for(v[i] = 0 , j = 1 ; j <= n ; j ++ )
v[i] += t[j] * a[j][i];
for(i = 1 ; i <= n ; i ++ )
{
for(sb = sc = 0 , j = 1 ; j <= n ; j ++ )
sb += v[j] * b[j][i] , sc += t[j] * c[j][i];
if(sb != sc) return 0;
}
}
return 1;
}
int main()
{
srand(20011011);
int n , i , j;
while(~scanf("%d" , &n))
{
for(i = 1 ; i <= n ; i ++ )
for(j = 1 ; j <= n ; j ++ )
scanf("%lld" , &a[i][j]);
for(i = 1 ; i <= n ; i ++ )
for(j = 1 ; j <= n ; j ++ )
scanf("%lld" , &b[i][j]);
for(i = 1 ; i <= n ; i ++ )
for(j = 1 ; j <= n ; j ++ )
scanf("%lld" , &c[i][j]);
if(judge(n)) puts("Yes");
else puts("No");
}
return 0;
}
最新文章
- Oracle汉字转拼音package
- Windows内核 字符串基本操作
- mysql 建表语句
- Qt 之 去除窗口部件被选中后的焦点虚线框(设置Qt::NoFocus即可)
- iOS 对UIButton的imageView和titleLabel进行重新布局
- JMeter中3种参数值的传递
- Python流程控制语句(Control Flow)
- 初涉JavaScript模式 (12) : 沙箱模式
- 自定义通用Distinct去除重复数据的2中方式
- 网络安全之IP伪造
- 黑苹果引导工具 Clover 配置详解及Clover Configurator使用
- vue监听滚动事件,实现滚动监听
- 微信小程序中-折线图
- 浅谈WPF中的MVVM框架--MVVMFoundation
- java.util中,util是什么意思
- Mysql Group by 使用解析
- Flannel网络插件配置
- SpringBoot之oauth2.0学习之服务端配置快速上手
- Git应用—01初始化项目
- 洛谷P2362 围栏木桩----dp思路