NOI2013向量内积

题目大意

两个d 维向量A=[a1,a2,...,ad]与B=[b1,b2,...,bd]的内积为其相对应维度的权值的乘积和
即:

编程任务:
对于给出的n个d维向量和一个整数k
找出两个向量满足内积为k的倍数,并输出。

数据范围:
11(1).png

解法一:枚举,暴力判断

时间复杂度:
期望得分:50

解法二:对于k=2的情况下压位优化

可以观察到,当k=2时
两个向量的内积等于其所对应的二进制数的与运算后的1的个数。
所以对于100位的二进制数我们可以压20位
也就是说将其分成5块分别计算
而对于计算1的个数可以预处理解决。

时间复杂度:
期望得分:60

解法三:随机算法

先考虑k=2的情况
以下运算全部在mod 2的环境下运行。
将n个向量压进一个的矩阵A1里。
设一个的矩阵A2满足

设矩阵
如果存在一对向量的内积为0
那么等价于矩阵P在非对角线位置上存在一个元素0。

对角线上的0元素干扰了我们的判断。
所以再设一个的矩阵F
满足 其他元素都为0。
由于只有对角线上的元素是非零的,所以可以用个数组存下F。

再设一个的矩阵G,元素全部为1。

再设一个矩阵T=G-F-P

至此,存在一对向量的内积为0已经等价于矩阵T中存在一个元素1。

但同时,计算这些矩阵的时间、空间复杂度都是巨大的。
我们也无法判断矩阵T是否存在元素1,更无法判断他在哪里。
我们一步步来。

随机一个的矩阵X
如果我们能求出矩阵L=,那么如果
那么T矩阵的第i行上就一定存在 一个元素1
剩下的事情就很容易了。

但问题是T是一个的矩阵,太巨大了,既存不下,也算不得,怎么办?

我们观察到:
什么意思?分配律!

G是一个元素全部为1的的矩阵,O(n)算出

F只有对角线上的元素非0,O(n)算出

而求可以利用结合律
的复杂度是O(dn)
再求,复杂度也是O(dn)

完美的避开了高复杂度的运算。

由于矩阵算出来没有1的概率是很小的,所以随机一定的次数大概就没问题了。

对于k=3的情况。 由于运算出来的结果除了0,1,还有2
所以上述方法就不能继续沿用了

但我们再进一步观察:
也就是说,如果我们求的是内积平方,那么问题就解决了。
但问题是如果求内积平方就不能用矩阵来做了。

所以我们再观察一下所谓的“内积平方”。
假设d=3吧。
向量A=[a1,a2,a3],向量B=[b1,b2,b3]

貌似就变成了:
向量A[a1a1,a1a2,a1a3,a2a1,a2a2,a2a3,a3a1,a3a2,a3a3]
向量B[b1b1,b1b2,b1b3,b2b1,b2b2,b2b3,b3b1,b3b2,b3b3]
两者的内积。
也就是说只要把d维向量变成上述维的向量
问题就和k=2的情况几乎完全相同了。
时间复杂度:
对于k=2:O(CND)
对于k=3:O(CND^2)
期望得分:100

comments powered by Disqus