一、题目
二、解法
发现本题 (k) 只有 (2,3) 两种取值，我们先考虑 (k=2) 的时候怎么做。
可以固定 (x_i)，去找有没有 (x_j) 合法。但是题目是不接受 (O(n^2d)) 判断的，可以考虑一些必要的判据，比如我们对 (jin[1,i)) 求出一个前缀和向量，然后和 (x_i) 点积。考虑如果全 (1) 的话点积的结果是 ((i-1)\% 2)，那么如果不满足这个条件说明一定有一对 ((i,j)) 满足 (x_i,x_j) 的点积为 (0)
这个判据是不充分的，所以我们把原序列 ( t random\_shuffle) 一下可以提高正确率。
考虑 (k=3) 的时候怎么做，还是要搞出一个对于前缀而言的必要判据，但是因为此时出现了 (2)，我们无法通过不全是某个数来推出存在某个数。考虑到 (2^2\%3=1)，那么我们维护点积平方的前缀和，就可以类似 (k=2) 的方法做了。
维护点积平方前缀和的方法就是考虑把平方拆开：
[(sum a_ib_i)^2=sum_{i}sum_{j}a_ib_icdot a_jb_j=sum_isum_j(a_ia_j)cdot(b_ib_j)
]
那么我们维护 (b_{i,j}) 表示第 (i) 位和第 (j) 位相乘的前缀和就可以快速计算了，时间复杂度 (O(nd^2))
三、总结
找到一组合法解可以先看某个范围内存不存在解，再去这个范围里找，至于判断某范围是否存在解可以用一些正确率较高的必要判据，再加之随机化就很难被卡掉。
所有优于存在，注意它们之间的转化，本题判断不全为 (1) 优于判断存在 (0)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 100005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,d,k,id[M],a[M][105],b[105][105];
int cal(int x,int y)
{
int r=0;
for(int i=1;i<=d;i++)
r+=a[x][i]*a[y][i];
return r;
}
int check(int x)
{
int r=0;
for(int i=1;i<=d;i++)
for(int j=1;j<=d;j++)
{
r+=b[i][j]*a[x][i]*a[x][j];
b[i][j]+=a[x][i]*a[x][j];
}
return r%k;
}
signed main()
{
n=read();d=read();k=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
a[i][j]=read()%k;
for(int t=1;t<=10;t++)
{
memset(b,0,sizeof b);
for(int i=1;i<=n;i++) id[i]=i;
random_shuffle(id+1,id+1+n);
for(int i=1;i<=n;i++)
if(check(id[i])!=(i-1)%k)
{
for(int j=1;j<i;j++)
if(cal(id[i],id[j])%k==0)
{
if(id[i]>id[j]) swap(i,j);
printf("%d %d
",id[i],id[j]);
return 0;
}
}
}
puts("-1 -1");
}