【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\)矩阵也没事。。我也不知道能不能卡

说点什么

您将是第一位评论人!

提醒
wpDiscuz