首页 > 代码库 > 3243: [Noi2013]向量内积 - BZOJ
3243: [Noi2013]向量内积 - BZOJ
Description
两个d 维向量A=[a1,a2,...,ad]与B=[b1,b2,...,bd]的内积为其相对应维度的权值的乘积和，即：
现有 n 个d 维向量x1,...,xn ，小喵喵想知道是否存在两个向量的内积为k的倍数。请帮助她解决这个问题
Input
第一行包含3个正整数n,d,k，分别表示向量的个数，维数以及待检测的倍数。
接下来n行每行有d个非负整数，其中第i行的第j个整数表示向量xi的第j维权值xi,j。
Output
包含两个整数，用空格隔开。
如果存在两个向量xp,xq的内积为k的整数倍，则输出两个向量的编号p与q（要求p<q）。如果存在多组这样的向量组合，输出其中任意一组即可。
若不存在这样的向量组合，则输出两个-1。
Sample Input
Sample Output
HINT
话说每次我都把题目复制一遍充字数2333
k=2时
我们把n个向量拼在一起，变成一个n*d的矩阵，设它为A，然后D=A*A’，A’为A的转置矩阵（行列互换），发现D[i,j]就表示向量i和向量j的内积
假设无解的话那么D矩阵除了对角线以外其他都是1，我们把无解的这个矩阵求出来设为C（只要求对角线），然后判断C和D是否相等，相等就无解
于是随机生成一个1*n的矩阵X判断X*A*A’是否等于X*C，假设不等于的话我们就找出不相等的那个位置，假设是第i个不相等，那就肯定存在一个j使得向量i与向量j的内积mod k=0
所以这个就暴力判断一下
k=3时
我们不能确定矩阵C的样子了，因为有三种情况0,1,2
但是我们发现1^2 mod 3=1，2^2 mod 3=1，所以我们让这个矩阵的元素都平方一下，那么矩阵C又变成了除了对角线其他都是1
但是前面又不好算了，其实也很好算，内积的平方拆开就变成了d^2维的向量的内积（空间存不下，直接照着式子算就行了）
其实随机生成矩阵不是很好，为0的话就没有用了，所以我直接用了全都是1的矩阵来跑答案
由于时间实在卡得太紧，我在Wikioi下了数据（可惜Wikioi没有spj）然后当提答题在bzoj上交了233
1 const 2 maxn=100100; 3 maxd=110; 4 var 5 a:array[0..maxn,0..maxd]of longint; 6 b,c,x,y:array[0..maxn]of longint; 7 n,d,k:longint; 8 9 procedure work2; 10 var 11 i,j,k,s:longint; 12 begin 13 s:=0; 14 for i:=1 to n do s:=s xor x[i]; 15 for i:=1 to n do c[i]:=s xor x[i] xor(x[i] and y[i]); 16 for i:=1 to n do 17 for j:=1 to d do 18 b[j]:=b[j] xor (x[i] and a[i,j]); 19 for i:=1 to d do x[i]:=b[i]; 20 for i:=1 to d do b[i]:=0; 21 for i:=1 to d do 22 for j:=1 to n do 23 b[j]:=b[j] xor (x[i] and a[j,i]); 24 for i:=1 to n do 25 if b[i]<>c[i] then 26 begin 27 for j:=1 to n do 28 if i<>j then 29 begin 30 s:=0; 31 for k:=1 to d do 32 s:=s xor (a[i,k] and a[j,k]); 33 if s=0 then 34 begin 35 writeln(i,‘ ‘,j); 36 exit; 37 end; 38 end; 39 end; 40 writeln(‘-1 -1‘); 41 end; 42 43 procedure work3; 44 var 45 i,j,k,s:longint; 46 begin 47 s:=0; 48 for i:=1 to n do if y[i]>0 then y[i]:=1; 49 for i:=1 to n do inc(s,x[i]); 50 for i:=1 to n do c[i]:=(s-x[i]+x[i]*y[i])mod 3; 51 for i:=1 to n do 52 for j:=1 to d do 53 for k:=1 to d do 54 inc(b[(j-1)*d+k],x[i]*a[i,j]*a[i,k]); 55 for i:=1 to d*d do 56 begin 57 x[i]:=b[i]mod 3; 58 b[i]:=0; 59 end; 60 for i:=1 to d do 61 for j:=1 to d do 62 for k:=1 to n do 63 inc(b[k],x[(i-1)*d+j]*a[k,i]*a[k,j]); 64 for i:=1 to n do b[i]:=b[i]mod 3; 65 for i:=1 to n do 66 if b[i]<>c[i] then 67 begin 68 for j:=1 to n do 69 if i<>j then 70 begin 71 s:=0; 72 for k:=1 to d do 73 s:=s+a[i,k]*a[j,k]; 74 if s mod 3=0 then 75 begin 76 writeln(i,‘ ‘,j); 77 exit; 78 end; 79 end; 80 end; 81 writeln(‘-1 -1‘) 82 end; 83 84 procedure main; 85 var 86 i,j:longint; 87 begin 88 read(n,d,k); 89 for i:=1 to n do 90 for j:=1 to d do 91 begin 92 read(a[i,j]); 93 a[i,j]:=a[i,j]mod k; 94 end; 95 for i:=1 to n do x[i]:=random(k); 96 for i:=1 to n do 97 for j:=1 to d do 98 y[i]:=y[i]+a[i,j]*a[i,j]; 99 for i:=1 to n do y[i]:=y[i]mod k;100 if k=2 then work2101 else work3;102 end;103 104 begin105 randomize;106 main;107 end.