首页 > 代码库 > [Noi2013]向量内积
[Noi2013]向量内积
来自FallDream的博客，未经允许，请勿转载，谢谢。
两个d 维向量A=[a1,a2,...,ad]与B=[b1,b2,...,bd]的内积为其相对应维度的权值的乘积和，即：
现有 n 个d 维向量x1,...,xn ，小喵喵想知道是否存在两个向量的内积为k的倍数。请帮助她解决这个问题
k=2时 n<=20000 d<=100 k=3时n<=1000,d<=100 或者n<=100000 d<=30
把两个向量内积看作矩阵一个1*d的矩阵和d*1的矩阵相乘
那么k=2的时候，就是一个n*d的矩阵和一个d*n的矩阵相乘，问得到的n*n的矩阵除了主对角线之外有没有0(mod k)
直接计算复杂度n^2d 所以不考虑计算它，而是转而判断得到的矩阵是否等于我想要的矩阵
假设n*d的矩阵为A，把它倒过来之后得到的d*n的矩阵为B，C=A*B，我期望的矩阵为D
矩阵D的主对角线的值可以O(nd)计算，其他值显然是1。
要判断C是否等于D，我可以转而随机一个n*1的向量T,判断C*T是否等于D*T即可
因为T只存在0和1，所以D*T可快速计算 而计算A*B*T时，我们可以先计算B*T,再计算A*(B*T),这两次计算都是O(nd)的
那么就做完了。复杂度O(nd)
但是k=3的时候，无法直接知道期望的矩阵，但是发现2^2=1(mod 3)
于是考虑计算E，Eij=Cij^2；矩阵D主对角线也对应平方一下
发现$Eij=(\sum Aik*Bkj)^{2}$ 展开后得到$Eij=\sum_{k1=1}^{d}\sum_{k2=1}^{d}Aik1*Bk1j*Aik2*Bk2j$
这个可以看作$n*d^{2}$的矩阵和一个$d^{2}*n$的矩阵相乘 之后就按照k=2的做法就行了 复杂度$O(nd^{2})$
但是这个办法并不能保证正确 如果直接让矩阵T都是1的话 在bzoj会被叉...
所以我们多随机几次就行了 一般都能过的吧
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define rint register int#define getchar() (*S++)char BB[1<<26],*S=BB;using namespace std;inline int read(){ int x = 0; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘) ch = getchar(); while(ch >= ‘0‘ && ch <= ‘9‘){x = x * 10 + ch - ‘0‘;ch = getchar();} return x;}int A[100005][105],B[100005],C[100005],D[100005],E[100005],n,d,K,cnt=0,sum=0,id[105][105];inline bool check(int a,int b){ int Sum=0; for(rint i=1;i<=d;++i) Sum+=A[a][i]*A[b][i]; return Sum%K==0;}inline void Solve(int x){ for(rint i=1;i<=n;++i) if(i!=x&&check(i,x)) {printf("%d %d\n",min(x,i),max(x,i));return;}}int main(){ fread(BB,1,1<<26,stdin); srand(23333U); n=read();d=read();K=read(); for(rint i=1;i<=n;++i) for(rint j=1;j<=d;++j) A[i][j]=read()%K; if(K==2) for(int It=1;It<=5;++It) { for(rint i=1;i<=n;++i) C[i]=rand()&1,sum+=C[i]; for(rint i=1;i<=n;++i) for(rint j=1;j<=d;++j) B[j]+=A[i][j]*C[i]; for(rint i=1;i<=d;++i) B[i]%=K; for(rint i=1;i<=n;++i) for(rint j=1;j<=d;++j) D[i]+=A[i][j]*B[j]; for(rint i=1;i<=n;++i) for(rint j=1;j<=d;++j) E[i]+=A[i][j]; for(rint i=1;i<=n;++i) E[i]=(E[i]*C[i]+sum-C[i])%K; for(rint i=1;i<=n;++i) if(E[i]!=(D[i]%K)) return Solve(i),0; sum=0; for(rint i=1;i<=n;++i) E[i]=D[i]=B[i]=0; } else for(int It=1;It<=5;++It) { for(rint i=1;i<=n;++i) C[i]=rand()%3,sum+=C[i]; for(rint i=1;i<=d;++i) for(rint j=1;j<=d;++j) id[i][j]=++cnt; for(rint k=1;k<=n;++k) for(rint i=1;i<=d;++i) for(rint j=1;j<=d;++j) B[id[i][j]]+=A[k][i]*A[k][j]*C[k]; for(rint i=1;i<=cnt;i++) B[i]%=K; for(rint i=1;i<=n;++i) for(rint j=1;j<=d;++j) for(rint k=1;k<=d;++k) D[i]+=A[i][j]*A[i][k]*B[id[j][k]]; for(rint i=1;i<=n;++i) for(rint j=1;j<=d;++j) E[i]+=A[i][j]*A[i][j]; for(rint i=1;i<=n;++i) E[i]%=K,E[i]=(E[i]*E[i]*C[i]+sum-C[i])%K; for(rint i=1;i<=n;++i) if(E[i]!=(D[i]%K)) return Solve(i),0; sum=0; for(rint i=1;i<=n;++i) E[i]=D[i]=B[i]=0; } return 0*puts("-1 -1");}
[Noi2013]向量内积