题目链接
题解
模数只有\(2\)或\(3\)，可以大力讨论
如果模数为\(2\)，乘积结果只有\(1\)或\(0\)
如果一个向量和前面所有向量乘积都为\(1\)，那么其和前面向量前缀和的乘积就唯一确定
我们维护向量前缀和，第一个乘积情况不符的向量一定是答案，然后再枚举另一个向量即
\(O(nd)\)
如果模数为\(3\)，乘积如果不为\(0\)，还可以为\(1\)或\(2\)，我们讨论的方法就不适用了
其实还是可以的
\[1^2 = 2^2 = 1 \pmod 3
\]
我们只要维护平方和即可
如何维护平方和?
\[(\sum\limits_{i = 1}^{d} a_ib_i)^2 = \sum\limits_{i = 1}^{d} \sum\limits_{j = 1}^{d} a_ia_jb_ib_j
\]
就相当于原来的\(d\)维向量变成了\(d^2\)维，\(O(nd^2)\)也是可以过的
#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 100005,maxm = 105,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int n,d,P;
int a[maxn][maxm],id[maxn];
int sum[maxm],Sum[maxm][maxm];
int mult(int* a,int* b){
int re = 0;
for (int i = 1; i <= d; i++) re = (re + a[i] * b[i] % P) % P;
return re;
}
int Mult(int a[],int b[][maxm]){
int re = 0;
for (int i = 1; i <= d; i++)
for (int j = 1; j <= d; j++)
re = (re + a[i] * a[j] * b[i][j] % P) % P;
return re;
}
void solve1(){
for (int i = 1; i <= d; i++) sum[i] = a[id[1]][i];
for (int i = 2; i <= n; i++){
int t = mult(a[id[i]],sum);
if (t != ((i - 1) & 1)){
for (int k = 1; k < i; k++)
if (!mult(a[id[k]],a[id[i]])){
printf("%d %d\n",min(id[k],id[i]),max(id[i],id[k]));
break;
}
return;
}
for (int j = 1; j <= d; j++) sum[j] = (sum[j] + a[id[i]][j]) % P;
}
printf("-1 -1\n");
}
void solve2(){
for (int i = 1; i <= d; i++)
for (int j = 1; j <= d; j++)
Sum[i][j] = a[id[1]][i] * a[id[1]][j] % P;
for (int i = 2; i <= n; i++){
int t = Mult(a[id[i]],Sum);
if (t != (i - 1) % P){
for (int k = 1; k < i; k++)
if (!mult(a[id[k]],a[id[i]])){
printf("%d %d\n",min(id[k],id[i]),max(id[i],id[k]));
break;
}
return;
}
for (int j = 1; j <= d; j++)
for (int k = 1; k <= d; k++)
Sum[j][k] = (Sum[j][k] + a[id[i]][j] * a[id[i]][k] % P) % P;
}
printf("-1 -1\n");
}
int main(){
srand(time(NULL));
n = read(); d = read(); P = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= d; j++)
a[i][j] = read() % P;
for (int i = 1; i <= n; i++) id[i] = i;
random_shuffle(id + 1,id + 1 + n);
if (P == 2) solve1();
else solve2();
return 0;
}
