把所有向量组合成一个$n\times d$的矩阵$A$，那么问题其实就是判断$AA^T=B$除了对角线上是否存在$0$（模$k$意义下）.
先忽略对角线这个问题，判断$B$中是否存在$0$，如果$k=2$，其实就是要判断$B$是否为全$1$矩阵. 判断是否相等有一个套路，就是随机一个$1\times n$的向量$X$，判断$XAA^T$是否等于$XB$，这样时间复杂度降至$\mathcal O(nd)$. 如果判断发现相等，错误率为$\frac{1}{2}$，重复若干次即可让错误率足够小.
下面考虑$k=3$的情况. 如果$B$中不存在$0$，$B$中的元素仍可能为$1$或$2$. 定义$C _{i,j}=B _{i,j}^2$，那么如果$B$中不存在$0$，则$C$为全$1$矩阵，关键是表示出这个$C$. 注意到
于是把输入的$d$维向量都变成$d^2$维的向量，就可以处理$k=3$的情况了.
接下来处理对角线. 注意到我们可以直接在$\mathcal O(nd)$的时间内把对角线计算出来，那么$XB$考虑对角线之后的值也可以高效算得.
代码：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
67
68
69
70
71
72
73
74
75
using namespace std;
namespace io{
static const ele size=1<<20;
char buf[size],*s=buf,*t=buf;
inline char gc(){
return s==t && (t=(s=buf)+fread(buf,1,size,stdin)),s==t?EOF:*s++;
}
template<class I>inline void gi(I&a){
char c;
while ((c=gc())<'0' || c>'9');
a=c-'0';
while ((c=gc())>='0' && c<='9') a=(a<<3)+(a<<1)+c-'0';
}
}
using io::gi;
const ele mul[3][3]={{0,0,0},{0,1,2},{0,2,1}};
ele n,d,d1,k,a[maxn][maxd],b[maxn],c[10000],dg[maxn],dst[maxn],p[10000],q[10000];
inline ele A(ele i,ele j){
return k==2?a[i][j]:mul[a[i][p[j]]][a[i][q[j]]];
}
inline ele& add(ele&a,ele b){
return a+b>=k?((a+=b)-=k):(a+=b);
}
int main(){
gi(n); gi(d); gi(k); d1=k==2?d:d*d;
for (int i=0; i<n; ++i)
for (int j=0; j<d; ++j) gi(a[i][j]),a[i][j]%=k;
for (int i=0; i<d; ++i)
for (int j=0; j<d; ++j) p[i*d+j]=i,q[i*d+j]=j;
for (int i=0; i<n; ++i){
dg[i]=0;
for (int j=0; j<d1; ++j) add(dg[i],A(i,j));
}
ele K=10;
while (K--){
ele s=0;
for (int i=0; i<n; ++i){
b[i]=rand()%k;
add(s,b[i]);
}
for (int i=0; i<n; ++i)
dst[i]=s,add(dst[i],mul[b[i]][dg[i]]-b[i]+k);
memset(c,0,sizeof(c));
for (int j=0; j<n; ++j)
for (int i=0; i<d1; ++i)
add(c[i],mul[b[j]][A(j,i)]);
memset(b,0,sizeof(b));
for (int i=0; i<n; ++i)
for (int j=0; j<d1; ++j)
add(b[i],mul[c[j]][A(i,j)]);
for (int i=0; i<n; ++i)
if (b[i]!=dst[i]){
for (int j=0; j<n; ++j){
if (i==j) continue;
ele s1=0;
for (int r=0; r<d; ++r)
add(s1,mul[a[i][r]][a[j][r]]);
if (!s1){
printf("%d %d\n",min(i,j)+1,max(i,j)+1);
return 0;
}
}
}
}
puts("-1 -1");
return 0;
}