- 题意：给出A,B,C三个矩阵（大小分别为n*p,p*m,n*m），C为给出的A*B结果，但是可能会有错，而错最多是一个。
- 题解：
- N^3必挂
- 然后这题是关于矩阵的判错
- 关于矩阵判错，我们常用几组随机数以大概率来判断
- 但是这题需要找到错误的位置以及该位置正确的答案
- 我们注意到，如果我们只需要得到矩阵C每一行的值的和，我们只需要将矩阵B每行相加成为一个px1的矩阵，这样只需要O(n^2)的复杂度
- 这样我们将给出的C矩阵的行和求出并进行判断即可判断出是否有错并且得到错误的行数
- 再在错误行中进行O(n^2)计算即可
//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan_d(T &ret) {
char c;
int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
inline void outt(int x) {
if(x>9) outt(x/10);
putchar(x%10+'0');
}
const int maxn=1e3+10;
int A[maxn][maxn];
int B[maxn][maxn];
int C[maxn][maxn];
int sum_b[maxn];
ll sum_c[maxn];
int main(){
int n,p,m;
scan_d(n),scan_d(p),scan_d(m);
rep(i,1,n)
rep(j,1,p)
scan_d(A[i][j]);
CLR(sum_b);
rep(i,1,p)
rep(j,1,m)
scan_d(B[i][j]),sum_b[i]+=B[i][j];
CLR(sum_c);
rep(i,1,n)
rep(j,1,m)
scan_d(C[i][j]),sum_c[i]+=C[i][j];
int sign=0;
rep(i,1,n){
ll ans=0;
rep(j,1,p){
ans+=A[i][j]*sum_b[j];
}
if(ans!=sum_c[i]){
sign=i;break;
}
}
if(sign==0){
cout<<"Yes"<<"\n";
return 0;
}else cout<<"No"<<"\n";
rep(i,1,m){
ll ans=0;
rep(j,1,p){
ans+=A[sign][j]*B[j][i];
}
if(ans!=C[sign][i]){
cout<<sign<<" "<<i<<"\n"<<ans<<"\n";
break;
}
}
return 0;
}
撰写