挺有意思的一道题
暴力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}{d}a_{i,k}a_{j,k})2$$$$sum_{j}sum_{k=1}{d}sum_{l=1}{d}a_{i,k}a_{j,k}a_{i,l}a_{j,l}$$$$sum_{k=1}{d}sum_{l=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
",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;
}