【BZOJ3243】【NOI2013】向量内积

我需要鬼畜常数优化

首先我们把所有向量排在一起构成矩阵\(A\)。

如果无解那么设\(B=A\times A^T\)，\(B\)除了对角线上的元素其他位置都不为\(0\)。

对于\(m=2\)的情况，其他位置都为\(1\)，只需要算出对角线上的元素然后判断\(A\times A^T=B\)是否成立。

判断是否成立的方法YMD以前考过：如果要判断\(A\times B=C\)是否成立，其中\(A\)为\(n\times m\)的矩阵，\(B\)为\(m\times k\)，\(C\)为\(n\times k\)，那么可以随机一个\(1\times n\)的矩阵\(D\)并判断\(D\times A\times B=D\times C\)是否成立即可。复杂度只有\(O(n^2)\)。

如果找到不同剩下的可以暴力查找

对于\(m=3\)的情况，其他位置可能为\(1\)或者\(2\)，可以发现在模\(3\)意义下它们的平方是相同的。

两个向量\(A,B\)的内积的平方

\((\sum_{i=1}^{d}A_iB_i)^2=\sum_{i=1}^{d}\sum_{j=1}^{d}A_iA_jB_iB_j\)

可以发现相当于把原来的向量变成了\(d^2\)维。那么和\(m=2\)的情况同样处理即可。

另外似乎直接判断乘起来是否是全\(1\)矩阵也没事。。我也不知道能不能卡