挺有意思的一道题
暴力60就是枚举每个向量暴力check,随机选向量就能多骗一些分
然后两个向量内积要模\(k\)为\(0\),那么如果全部不为\(0\)就不合法.先考虑\(k=2\),对于向量\(i\),假如前面所有向量和他的内积为\(1\),那么所有内积之和应该要和\(i-1\)模\(2\)同余,所以如果某个\(i\)不满足这个条件,就可以\(O(nd)\)的找出前面和他内积为\(0\)的向量.而内积之和可以看成当前向量和前面所有向量之和的内积,所以维护好前面向量的和,每次前缀和的当前的内积,复杂度为\(O(nd)\)
然后\(k=3\),内积不为\(0\),则可能为\(1,2\),然后可以发现\(1,2\)的平方模\(3\)是\(1\),那么判断条件就是前面内积平方和是否和\(i-1\)模\(3\)同余.前面内积平方和就是$$\sum_{j}(\sum_{k=1}2$$$$\sum_{j}\sum_{k=1}{d}a_{i,k}a_{j,k}a_{i,l}a_{j,l}$$$$\sum_{k=1}{d}a_{i,k}a_{i,l}\sum_{j}a_{j,k}a_{j,l}$$
维护后面那个前缀和就行了
注意可能会出现所有内积之和和\(i-1\)模\(k\)同余,那么我们需要把序列随机打乱后多做几遍
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define il inline
using namespace std;
const int N=1e5+10,M=100+10;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,d,kk,p[N],a[N][M];
int b[M];
int ck(int i)
{
int sm=0;
for(int k=1;k<=d;++k) sm=(sm+a[i][k]*b[k])%kk;
return sm;
}
int c[M][M];
int ckk(int i)
{
int sm=0;
for(int k=1;k<=d;++k)
for(int l=1;l<=d;++l)
sm=(sm+a[i][k]*a[i][l]*c[k][l])%kk;
return sm;
}
int main()
{
n=rd(),d=rd(),kk=rd();
for(int i=1;i<=n;++i) p[i]=i;
for(int i=1;i<=n;++i)
for(int j=1;j<=d;++j)
a[i][j]=rd()%kk;
int Q=5;
while(Q--)
{
random_shuffle(p+1,p+n+1);
if(kk==2) memset(b,0,sizeof(b));
else memset(c,0,sizeof(c));
for(int i=1;i<=n;++i)
{
if((kk==2?ck(p[i]):ckk(p[i]))!=(i-1)%kk)
{
for(int j=1;j<i;++j)
{
int sm=0;
for(int k=1;k<=d;++k) sm=(sm+a[p[i]][k]*a[p[j]][k])%kk;
if(!sm)
{
int x=min(p[i],p[j]),y=max(p[i],p[j]);
printf("%d %d\n",x,y);
return 0;
}
}
}
if(kk==2)
{
for(int k=1;k<=d;++k) b[k]=(b[k]+a[p[i]][k])%kk;
}
else
{
for(int k=1;k<=d;++k)
for(int l=1;l<=d;++l)
c[k][l]=(c[k][l]+a[p[i]][k]*a[p[i]][l])%kk;
}
}
}
puts("-1 -1");
return 0;
}