定义两个$d$维向量${A=[a_1,a_2....a_n]}$,${B=[b_1,b_2....b_n]}$的内积为其相对应维度的权值的乘积和:
$${\left \langle A,B \right \rangle= \sum _{i=1}^{d}a_i*b_i}$$
现在有$n$个$d$维向量，判断是否存在两个向量的内积为$k$的倍数${(2\leq k\leq 3)}$
我们考虑将$n$个$d$维的向量构成一个$n*d$的矩阵$A$，$A^{T}$为$A$的转置矩阵。
令矩阵${B=A*A^{t}}$,那么${B_{i,j}}$就表示了向量$i$,与向量$j$的内积。
直接判断内积的值即可。
但是这仅仅简化了题意，复杂度仍是${O(n^{2}d)}$，大概可以得到$50$分。
考虑$k=2$的情况(矩阵的取值均在模$2$的意义下进行讨论)
我们有一种经典的方法判定两个矩阵是否相等，我们只关心$0$元素是否存在。
令$C$为全$1$矩阵
在模$2$的意义下随机一个$1*n$的向量$X$。
根据矩阵乘法的结合律判断等式${X*A*A^{T}=X*C}$是否成立。
若是存在有一个元素不相同，表示对应列上出现了一个$0$向量，然后暴力寻找行的位置即可。
若是这一次没有找到,也许是根本就没有这样的向量或者是刚好在这个$X$向量的影响下判为了相等，多做几次，每次正确率约为$0.5$。
综合暴力至此可以得到$75$分。
考虑$k=3$的情况，为什么就不能像$k=2$的时候那样做了呢？
因为矩阵$B$中的元素可以是${{0,1,2}}$了，无法再和全$1$矩阵$C$比较。
想办法将$k=3$的情况转换为$k=2$的情况。
之所以不能像$k=2$做，是因为出现了结果为$2$的情况。
注意到一个性质：${2\equiv -1\left ( mod 3 \right )}$
因此，如果我们将矩乘之后的矩阵D的所有结果平方，那么C就能用全1矩阵了。
令${NEWA\left ( i,j \right )=D(i,j)^{2}}$
${\because NEWA\left ( i,j \right )=\sum _{k_1=1}^{d}\sum _{k_2=1}^{d}A(i,k_1)A(i,k_2)A(k1,j)A(k2,j)}$
你可以想象成可以把每一个$d$维向量$A$转化为了${d^{2}}$维向量$Z$,其中${Z_{(i-1)*d+j}=a_i*a_j (1\leq i,j\leq d)}$
${\therefore }$这个时候变成了${n*d^{2}}$的矩阵与${d^{2}*n}$的矩阵相乘。
之后的做法就与$k=2$的情况相同。
综合之前的分数可以获得$100$分
NOTICE：$k=3$的运算是在模$3$的意义下的，只是最后的结果平方之后的值只能为${{0,1}}$。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<ctime>
using namespace std;
#define maxn 100100
#define maxd 310
#define llg long long
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,a[maxn][maxd],d,k;
llg X[maxn],NX[maxn];
llg LX[maxn],Y[maxn],LY[maxn],T,g[maxn],l[maxn],r[maxn];
llg D;
bool pd=false; void init()
{
cin>>n>>d>>k;
for (llg i=;i<=n;i++)
for (llg j=;j<=d;j++)
{
scanf("%lld",&a[i][j]);
// at[j][i]=a[i][j];
g[i]+=a[i][j]*a[i][j]; g[i]%=k;
}
} void check(llg i,llg j)
{
llg sum=;
for (llg p=;p<=d;p++) sum+=a[i][p]*a[j][p];
sum%=k;
if (sum==)
{
if (i>j) swap(i,j);
printf("%lld %lld\n",i,j);
pd=true;
}
} inline void solve2()
{
memset(LX,,sizeof(LX)); memset(NX,,sizeof(NX));
llg tot=;
for (llg i=;i<=n;i++) X[i]=rand()%k,tot+=X[i],tot%=k;
for (llg i=;i<=d;i++)
for (llg j=;j<=n;j++)
NX[i]+=X[j]*a[j][i],NX[i]%=k;
for (llg i=;i<=n;i++)
for (llg j=;j<=d;j++)
LX[i]+=NX[j]*a[i][j],LX[i]%=k;
for (llg i=;i<=n;i++)
if (LX[i]!=tot)
{
for (llg j=;j<=n;j++)
if (i!=j)
{
if (pd) return ;
check(i,j);
}
}
} void solve3()
{
memset(LX,,sizeof(LX)); memset(NX,,sizeof(NX));
llg tot=;
for (llg i=;i<=n;i++) X[i]=rand()%k,tot+=X[i];
tot%=k;
for (llg j=;j<=n;j++)
for (llg i=;i<=D;i++) NX[i]+=X[j]*a[j][l[i]]*a[j][r[i]];
for (llg i=;i<=n;i++)
{
for (llg j=;j<=D;j++) LX[i]+=NX[j]*a[i][l[j]]*a[i][r[j]];
LX[i]+=(-g[i])*X[i]; LX[i]%=k; LX[i]+=k;
if (LX[i]%k!=tot)
{
for (llg j=;j<=n;j++)
if (i!=j)
{
if (pd) return;
check(i,j);
}
llg he=;
}
}
} int main()
{
yyj("a");
srand(time(NULL));
init();
if (k==)
{
T=;
while (T--)
{
solve2();
if (pd) return ;
}
}
else
{
T=;
for (llg i=;i<=n;i++) g[i]*=g[i],g[i]%=k;
D=d*d;
for (llg i=;i<=D;i++)
{
llg t=(i%d==)?i/d:i/d+;
l[i]=t,r[i]=i-(t-)*d;
}
while (T--)
{
solve3();
if (pd) return ;
}
}
if (!pd) cout<<"-1 -1";
return ;
}
HACK(若取全1矩阵C,但C的对角线均设为了0):
${A*A^{T}}$
全${1}$向量${X}$
${A*X*A^{t}}$
${C*X}$
将误判为相等。