#2664. 「NOI2013」向量内积
两个 (d) 维向量 (A=[a_1, a_2 ,...,a_d]) 与 (B=[b_1 ,b_2 ,...,b_d]) 的内积为其相对应维度的权值的乘积和，即：
现有 (n) 个 (d) 维向量 (x_1, ldots, x_n)，小喵喵想知道是否存在两个向量的内积为 (k) 的倍数。请帮助她解决这个问题。
输入格式
第一行包含 (3) 个正整数 (n,d,k)，分别表示向量的个数、维数以及待检测的倍数。
接下来 (n) 行每行有 (d) 个非负整数，其中第 (i) 行的第 (j) 个整数表示向量 ([x_i]) 的第 (j) 维权值 (x_{i,j})。
输出格式
包含两个整数，用空格隔开。
如果存在两个向量 (x_p,x_q) 的内积为 (k) 的整数倍，则输出两个向量的编号 (p) 与 (q)（要求 (p<q)）。如果存在多组这样的向量组合，输出其中任意一组即可。
若不存在这样的向量组合，则输出两个 (−1)。
数据范围与提示
| 测试点编号 | n | d | k | (x_i) |
|---|---|---|---|---|
| (1) | (2) | (20) | (2) | (le 10) |
| (2) | (5) | (20) | (2) | (le 10) |
| (3) | (10) | (20) | (3) | (le 10) |
| (4) | (20) | (20) | (2) | (le 100) |
| (5) | (50) | (20) | (3) | (le 100) |
| (6) | (50) | (50) | (2) | (le 1000) |
| (7) | (50) | (50) | (3) | (le 3000000) |
| (8) | (80) | (80) | (2) | (le 2000000) |
| (9) | (100) | (100) | (3) | (le 3000000) |
| (10) | (500) | (100) | (3) | (le 3000000) |
| (11) | (1000) | (100) | (2) | (le 2000000) |
| (12) | (1000) | (100) | (3) | (le 3000000) |
| (13) | (10000) | (100) | (2) | (< 10) |
| (14) | (10000) | (100) | (3) | (< 10) |
| (15) | (15000) | (100) | (2) | (< 10) |
| (16) | (18000) | (100) | (2) | (< 10) |
| (17) | (20000) | (100) | (2) | (< 10) |
| (18) | (50000) | (30) | (3) | (< 10) |
| (19) | (80000) | (30) | (3) | (< 10) |
| (20) | (100000) | (30) | (3) | (< 10) |
向量点乘的过程有点像一个行向量和一个列向量相乘，然后我们把原始向量排成一个矩阵(A),然后令(D=A*A^T)。
那么(D_{i,j})就代表向量(i)和向量(j)做内积。
突破口在(mod 2)上。
现在矩阵所有元素在(mod 2)下
我们设一个(n imes n)的全(1)矩阵(E)，然后通过一些随机化的方法比较(D)和(E)有哪里不相等。
我们可以随机几个(1 imes n)的向量(C)，然后判断是否有
并且我们可以判断出哪一行不相等，然后可以暴力枚举与之匹配的另一个。
或者随机一下原始向量的排列顺序。
至于为什么随机次数是常数次，可以从Hash的角度感性理解
然后(mod 3)也差不多
注意到(2^2equiv 1pmod 3,1^2equiv 1pmod 3)，我们把矩阵(D'_{i,j}=D^2_{i,j})搞出来就可以了
把这个式子拆开可以发现我们需要把组成(A)的每一个向量搞出(1 imes d^2)的，即(A'_{i,(j-1)d+k}=A_{i,j}*A_{i,k})
然后和(2)是一样的
Code:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <algorithm>
int read()
{
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}
int n,d,k;
namespace beecute
{
int yuy[20010][110],bee[110],dew[20010],c[20010];
void work()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
yuy[i][j]=read()&1;
int Dew=5;
while(Dew--)
{
memset(dew,0,sizeof dew);
memset(bee,0,sizeof bee);
for(int i=1;i<=n;i++) c[i]=rand()&1;
for(int i=1;i<=d;i++)
for(int j=1;j<=n;j++)
if(c[j])
bee[i]=bee[i]+yuy[j][i]&1;
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
dew[i]=(dew[i]+bee[j]*yuy[i][j])&1;
for(int i=1;i<=n;i++)
if(dew[i]!=c[i])
{
for(int j=1;j<=n;j++)
{
int sum=0;
for(int k=1;k<=d;k++)
sum=(sum+yuy[i][k]*yuy[j][k])&1;
if(!sum)
{
if(i<j) printf("%d %d
",i,j);
else printf("%d %d
",j,i);
return;
}
}
}
}
puts("-1");
}
}
namespace beelovely
{
int yuy[100010][101],bee[10010],dew[100010],c[100010];
void work()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
yuy[i][j]=read()%3;
for(int i=1;i<=d;i++)
for(int j=1;j<=d;j++)
for(int k=1;k<=n;k++)
(bee[(i-1)*d+j]+=yuy[k][i]*yuy[k][j])%=3;
int Dew=5;
while(Dew--)
{
memset(dew,0,sizeof dew);
memset(bee,0,sizeof bee);
for(int i=1;i<=n;i++) c[i]=rand();
for(int i=1;i<=d;i++)
for(int k=1;k<=n;k++)
if(c[k])
bee[i]=(bee[i]+yuy[k][i]*yuy[k][j])%3;
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
for(int k=1;k<=d;k++)
dew[i]=(dew[i]+bee[(j-1)*d+k]*yuy[p[i]][j]*yuy[p[i]][k])%3;
for(int i=1;i<=n;i++)
if(dew[i]!=c[i])
{
for(int j=1;j<=n;j++)
{
int sum=0;
for(int k=1;k<=d;k++)
sum=(sum+yuy[i][k]*yuy[j][k])&1;
if(!sum)
{
if(i<j) printf("%d %d
",i,j);
else printf("%d %d
",j,i);
return;
}
}
}
}
puts("-1");
}
}
int main()
{
n=read(),d=read(),k=read();
if(k==2) beecute::work();
else beelovely::work();
return 0;
}
2019.2.11