题目链接：点击查看
题目大意：给出一个二维矩阵表示无限大的乘法表，每个位置的值都等于 i * j ，现在给出一个 n * m 的矩阵，现在需要判断该矩阵是否为乘法表的一个子矩阵
题目分析：训练时以为是联立方程然后高斯消元求秩，但时间复杂度顶不太住，于是就自己解方程去求秩，很显然这么庞大的代码实现写出了一堆bug，最后都到了懒得修改的地步
看了网上的题解后人都傻了，应该是正解，随便选一个位置枚举其因子作为 i 和 j ，然后 O( n * m ) 去扫一遍整个矩阵然后判断是否合法，但 1e9 内因子最多的一个数只有 1536 ，总的算下来时间复杂度也是 1e11 级别的，但最后 800ms 就过了，那就只能说明这个题目的数据应该比较难构造
然后就转换成一个简单的模拟题了，随便写写就好了
代码：
#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> #define double long double using namespace std; typedef long long LL; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const int N=1e5+100; vector<tuple<int,int,int>>node; bool check(LL x,LL y) { for(auto t:node) { LL i,j,num; tie(i,j,num)=t; if((i+x)*(j+y)!=num) return false; } return true; }; bool solve() { if(node.empty()) return true; int num,x,y; tie(x,y,num)=node.front(); for(int i=1;i*i<=num;i++) { if(num%i) continue; int a=i,b=num/i; if(a>=x&&b>=y&&check(a-x,b-y)) return true; if(b>=x&&a>=y&&check(b-x,a-y)) return true; } return false; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif ios::sync_with_stdio(false); int w; cin>>w; int kase=0; while(w--) { node.clear(); int n,m; cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { string s; cin>>s; if(s=="?") continue; node.emplace_back(i,j,stoi(s)); } if(solve()) cout<<"Case #"<<++kase<<": Yes"<<endl; else cout<<"Case #"<<++kase<<": No"<<endl; } return 0; }
