#2664. 「NOI2013」向量内积
两个 \(d\) 维向量 \(A=[a_1, a_2 ,...,a_d]\) 与 \(B=[b_1 ,b_2 ,...,b_d]\) 的内积为其相对应维度的权值的乘积和，即：
\[ (A,B) = \displaystyle \sum_{i=1}^d{a_ib_i} = a_1b_1 + a_2b_2 + \ldots + a_db_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\)做内积。
突破口在\(\bmod 2\)上。
现在矩阵所有元素在\(\bmod 2\)下
我们设一个\(n\times n\)的全\(1\)矩阵\(E\)，然后通过一些随机化的方法比较\(D\)和\(E\)有哪里不相等。
我们可以随机几个\(1\times n\)的向量\(C\)，然后判断是否有
\[ C\times A\times A^T\equiv C\times E\pmod 2 \] 并且我们可以判断出哪一行不相等，然后可以暴力枚举与之匹配的另一个。或者随机一下原始向量的排列顺序。
至于为什么随机次数是常数次，可以从Hash的角度感性理解
然后\(\bmod 3\)也差不多
注意到\(2^2\equiv 1\pmod 3,1^2\equiv 1\pmod 3\)，我们把矩阵\(D'_{i,j}=D^2_{i,j}\)搞出来就可以了
把这个式子拆开可以发现我们需要把组成\(A\)的每一个向量搞出\(1\times d^2\)的，即\(A'_{i,(j-1)d+k}=A_{i,j}*A_{i,k}\)
然后和\(2\)是一样的
Code:
#include#include #include #include #include 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
2019.2.11