给定一个$3\times 3$的矩阵$a$(已知)和数组$A_1,…,A_3$(
未知
)和数组$B_1,…,B_3$(未知
),且满足$a_{ij}=A_i+B_j$,判断是否存在这样的两个数组使得该矩阵成立?
-
当矩阵$a$中的元素都$\le 100$时,可用$O(n^3)$的时间复杂度解决(此处不给出解释和代码);
-
当矩阵$a$中的元素都$\> 100$时;
分析:
假设$A_1$存在
- $A_1=A_1$
- $B_1=a_{11}-A_1$
- $A_2=a_{21}-B_1=a_{21}-a_{11}+A_1$
- $B_2=a_{22}-A_2=a_{22}-a_{21}+a_{11}-A_1$
- $A_3=a_{31}-B_1=a_{31}-a_{11}+A_1$
- $B_3=a_{33}-A_2=a_{33}-a_{31}+a_{11}-A_1$
由上整理可得:
- $a_{12}=A_1+B_2=A_1+a_{22}-a_{21}+a_{11}-A_1=a_{22}-a_{21}+a_{11}$
- $a_{13}=A_1+B_3=A_1+a_{33}-a_{31}+a_{11}-A_1=a_{33}-a_{31}+a_{11}$
- $a_{23}=A_2+B_3=a_{21}-a_{11}+A_1+a_{33}-a_{31}+a_{11}-A_1=a_{33}+a_{21}-a_{31}$
- $a_{32}=A_3+B_2=a_{31}-a_{11}+A_1+a_{22}-a_{21}+a_{11}-A_1=a_{31}+a_{22}-a_{21}$
综上判断$4$项结果即可
// Problem: C - Takahashi's Information
// Contest: AtCoder - AtCoder Beginner Contest 088
// URL: https://atcoder.jp/contests/abc088/tasks/abc088_c
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date: 2023-04-07 20:25:40
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 4
using namespace std;
typedef long long ll;
int a[MAXN][MAXN];
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
cin >> a[i][j];
if(a[1][2]==a[2][2]-a[2][1]+a[1][1]&&
a[1][3]==a[3][3]-a[3][1]+a[1][1]&&
a[2][3]==a[3][3]+a[2][1]-a[3][1]&&
a[3][2]==a[3][1]+a[2][2]-a[2][1])
cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}