我需要鬼畜常数优化
首先我们把所有向量排在一起构成矩阵\(A\)。
如果无解那么设\(B=A\times A^T\),\(B\)除了对角线上的元素其他位置都不为\(0\)。
对于\(m=2\)的情况,其他位置都为\(1\),只需要算出对角线上的元素然后判断\(A\times A^T=B\)是否成立。
判断是否成立的方法YMD以前考过:如果要判断\(A\times B=C\)是否成立,其中\(A\)为\(n\times m\)的矩阵,\(B\)为\(m\times k\),\(C\)为\(n\times k\),那么可以随机一个\(1\times n\)的矩阵\(D\)并判断\(D\times A\times B=D\times C\)是否成立即可。复杂度只有\(O(n^2)\)。
如果找到不同剩下的可以暴力查找
对于\(m=3\)的情况,其他位置可能为\(1\)或者\(2\),可以发现在模\(3\)意义下它们的平方是相同的。
两个向量\(A,B\)的内积的平方
\((\sum_{i=1}^{d}A_iB_i)^2=\sum_{i=1}^{d}\sum_{j=1}^{d}A_iA_jB_iB_j\)
可以发现相当于把原来的向量变成了\(d^2\)维。那么和\(m=2\)的情况同样处理即可。
另外似乎直接判断乘起来是否是全\(1\)矩阵也没事。。我也不知道能不能卡
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
// <3243.cpp> - Thu Feb 16 20:42:12 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } #define rep(i,n) for(int i=1;i<=n;i++) const int MAXN=100010; const int INF=1e9; int n,d,mod,a[MAXN][110],cnt[MAXN]; int p[MAXN],A[MAXN],B[MAXN],C[MAXN]; void get(int x){ rep(i,n){ if(x==i)continue; int sum=0; rep(j,d)sum=(sum+a[x][j]*a[i][j])%mod; if(!sum){printf("%d %d\n",min(x,i),max(x,i));exit(0);} } } void work2(){ int s=0; rep(i,n)s=(s+(p[i]=rand()%mod))%mod; rep(i,d)A[i]=0; rep(i,n)B[i]=0; rep(j,n)rep(i,d)(A[i]+=p[j]*a[j][i])%=mod; rep(i,n)rep(j,d)(B[i]+=A[j]*a[i][j])%=mod; rep(i,n){C[i]=s;if(!cnt[i])C[i]=(C[i]-p[i]+mod)%mod;} rep(i,n)if(B[i]!=C[i])get(i); } int id[110][110]; void work3(){ int s=0,t=0; rep(i,n)s=(s+(p[i]=rand()%mod))%mod; rep(i,d)rep(j,d)A[id[i][j]=++t]=0; rep(i,n)B[i]=0; rep(i,n)rep(j,d)rep(k,d)(A[id[j][k]]+=p[i]*a[i][j]*a[i][k])%=mod; rep(i,n)rep(j,d)rep(k,d)(B[i]+=A[id[j][k]]*a[i][j]*a[i][k])%=mod; rep(i,n){C[i]=s;if(!cnt[i])C[i]=(C[i]-p[i]+mod)%mod;} rep(i,n)if(B[i]!=C[i])get(i); } int main(){ srand(19260817); n=gi(),d=gi(),mod=gi(); rep(i,n)rep(j,d){ a[i][j]=gi()%mod; cnt[i]=(cnt[i]+a[i][j]*a[i][j])%mod; } int T=2; while(T--)mod==2?work2():work3(); printf("-1 -1"); return 0; } |