鉴于NOI吧已死，LZ就来这里讲(pian)讲(pian)题(jing)目(yan) = =。。。
首先呢，暴力O(N^2D)就不用说了……压位的暴力也不用说了……不过k=3的位运算优化还是要略微费点脑筋的……
接下来的高端做法呢大概我现在想到看到的就两种：
1）标程的做法：随机
先看k=2。以下在模2意义下讨论。假设以这些向量为列向量的矩阵为A=(a1,a2,...,an)，那么这题也就是说要找出A'*A除了对角线上的元素以外为0的一个元素，这里A'是将A行列对换所得矩阵（转置）。首先要去掉【不在对角线】的限制。这个比较简单，暴力求出对角线上的元素，然后如果该元素为0，在新矩阵B的这个位置放上1。当然B是个对角矩阵，只有对角线上有元素，可以用数组存……下面其实就是寻找J-A'*A-B的非零元，其中J是所有元素都是1的矩阵。注意到这个矩阵我们其实不能算出来，但是对于向量X，A'*A*X是可以很快算出的。这是由于矩阵乘法有结合律，右结合地算（A'*(A*X)）复杂度只有O(ND)。于是随机一个向量X，求J*X-A'*A*X-B*X，三项都能很快求出，然后看所得的向量哪个元素不为0，所求的位置肯定在A'*A对应的那一行上，然后暴力枚举即可。复杂度是O(CND)，其中C是随机次数。
再看k=3。k=3的问题在于，如果看A'*A，这题还是要求一个不在对角线上的零元素，但是A'*A每个元素在模3意义下除了可能为0、1，还可能是2，不能转化为求J-A'*A-B的非零元，比较难办。注意到1*1=1,2*2=1(mod 3)，内积平方不是0就是1，因而我们可以考虑判定是否内积平方是0。然而(x1y1+...+xnyn)^2=x1^2y1^2+x1x2y1y2+...+x1xny1yn+x2x1y2y1+...+x2xny2yn+...+xnx1yny1+...+xn^2yn^2，(x1,...,xn)与(y1,...,yn)内积平方转化成(x1^2,x1x2,...,x1xn,x2x1,...,x2xn,xnx1,...,xn^2)与(y1^2,y1y2,...,y1yn,y2y1,...,y2yn,yny1,...,yn^2)的内积。这些导出向量是D^2维的，于是问题转化成D^2维下类似k=2的情况。复杂度是O(CND^2)。
另外对于非零矩阵，一次随机乘出来恰好是零向量的概率<=1/k(?)，所以随机10次以后仍然判定失误的概率还是很低的。
=================================================================================
=====================对于只想AC的同学，以下的就不用看了。。。====================
===================================高能慎入。。==================================
=================================================================================
2）另一种确定性做法
还是先看k=2。如果真的没有两个向量正交，也就是A'*A除了对角线都是1，那么对角线上的0个数不可能多于D+1。这是由于rank(A'*A)<=rank(A)，rank(A)<=D，所以rank(A'*A)<=D。又可以发现，如果对角线上有k个0，这k行向量组的秩最少为2[k/2]>=k-1。如果有多于D+1个0在对角线上，其秩必然大于D，矛盾。所以先把对角线上是0，也就是自身内积是0的向量单独分出来，这些向量若多于D+1个，其中肯定有与其他向量正交的向量。这时候将前D+2个与所有向量暴力检查一遍，如果找到了直接输出。下面只考虑自身内积为1的向量。用高斯消元求出这些向量的一个极大无关组，并同时求出每个向量在这个极大无关组下的坐标。首先检验，极大无关组内是否有正交的。对于其他向量，若X、Y是某两个向量在这个无关组下的坐标，那么由于该极大无关组度量矩阵是J，则它们的内积可以表示为X'*J*Y，可以发现，它们内积为1当且仅当X、Y每一维加起来都是奇数。但是，如果X（或Y）每一维加起来是偶数，那么X'*J*X已经为0，也就是它代表的向量的自身内积为0，矛盾。所以此时不可能找到正交向量对。时间复杂度：自身内积0的向量检查O(ND^2)，高斯消元O(ND^2)，检验O(D^3)，总复杂度O(ND^2)，比随机做法慢一截。
再看k=3。这里思路就差不多了，和之前随机做法一样转化成D^2维的问题，然后仿照之前的做。但是这里总复杂度要达到O(ND^4)，对于这题完全无法承受。
最后是，此题完全可以构造只有一对向量正交的情况，所以不要抱有过多侥幸心理。。。
最后的最后是，如果有人能想到时间复杂度更低的随机/确定性做法，欢迎与我讨论。
首先呢，暴力O(N^2D)就不用说了……压位的暴力也不用说了……不过k=3的位运算优化还是要略微费点脑筋的……
接下来的高端做法呢大概我现在想到看到的就两种：
1）标程的做法：随机
先看k=2。以下在模2意义下讨论。假设以这些向量为列向量的矩阵为A=(a1,a2,...,an)，那么这题也就是说要找出A'*A除了对角线上的元素以外为0的一个元素，这里A'是将A行列对换所得矩阵（转置）。首先要去掉【不在对角线】的限制。这个比较简单，暴力求出对角线上的元素，然后如果该元素为0，在新矩阵B的这个位置放上1。当然B是个对角矩阵，只有对角线上有元素，可以用数组存……下面其实就是寻找J-A'*A-B的非零元，其中J是所有元素都是1的矩阵。注意到这个矩阵我们其实不能算出来，但是对于向量X，A'*A*X是可以很快算出的。这是由于矩阵乘法有结合律，右结合地算（A'*(A*X)）复杂度只有O(ND)。于是随机一个向量X，求J*X-A'*A*X-B*X，三项都能很快求出，然后看所得的向量哪个元素不为0，所求的位置肯定在A'*A对应的那一行上，然后暴力枚举即可。复杂度是O(CND)，其中C是随机次数。
再看k=3。k=3的问题在于，如果看A'*A，这题还是要求一个不在对角线上的零元素，但是A'*A每个元素在模3意义下除了可能为0、1，还可能是2，不能转化为求J-A'*A-B的非零元，比较难办。注意到1*1=1,2*2=1(mod 3)，内积平方不是0就是1，因而我们可以考虑判定是否内积平方是0。然而(x1y1+...+xnyn)^2=x1^2y1^2+x1x2y1y2+...+x1xny1yn+x2x1y2y1+...+x2xny2yn+...+xnx1yny1+...+xn^2yn^2，(x1,...,xn)与(y1,...,yn)内积平方转化成(x1^2,x1x2,...,x1xn,x2x1,...,x2xn,xnx1,...,xn^2)与(y1^2,y1y2,...,y1yn,y2y1,...,y2yn,yny1,...,yn^2)的内积。这些导出向量是D^2维的，于是问题转化成D^2维下类似k=2的情况。复杂度是O(CND^2)。
另外对于非零矩阵，一次随机乘出来恰好是零向量的概率<=1/k(?)，所以随机10次以后仍然判定失误的概率还是很低的。
=================================================================================
=====================对于只想AC的同学，以下的就不用看了。。。====================
===================================高能慎入。。==================================
=================================================================================
2）另一种确定性做法
还是先看k=2。如果真的没有两个向量正交，也就是A'*A除了对角线都是1，那么对角线上的0个数不可能多于D+1。这是由于rank(A'*A)<=rank(A)，rank(A)<=D，所以rank(A'*A)<=D。又可以发现，如果对角线上有k个0，这k行向量组的秩最少为2[k/2]>=k-1。如果有多于D+1个0在对角线上，其秩必然大于D，矛盾。所以先把对角线上是0，也就是自身内积是0的向量单独分出来，这些向量若多于D+1个，其中肯定有与其他向量正交的向量。这时候将前D+2个与所有向量暴力检查一遍，如果找到了直接输出。下面只考虑自身内积为1的向量。用高斯消元求出这些向量的一个极大无关组，并同时求出每个向量在这个极大无关组下的坐标。首先检验，极大无关组内是否有正交的。对于其他向量，若X、Y是某两个向量在这个无关组下的坐标，那么由于该极大无关组度量矩阵是J，则它们的内积可以表示为X'*J*Y，可以发现，它们内积为1当且仅当X、Y每一维加起来都是奇数。但是，如果X（或Y）每一维加起来是偶数，那么X'*J*X已经为0，也就是它代表的向量的自身内积为0，矛盾。所以此时不可能找到正交向量对。时间复杂度：自身内积0的向量检查O(ND^2)，高斯消元O(ND^2)，检验O(D^3)，总复杂度O(ND^2)，比随机做法慢一截。
再看k=3。这里思路就差不多了，和之前随机做法一样转化成D^2维的问题，然后仿照之前的做。但是这里总复杂度要达到O(ND^4)，对于这题完全无法承受。
最后是，此题完全可以构造只有一对向量正交的情况，所以不要抱有过多侥幸心理。。。
最后的最后是，如果有人能想到时间复杂度更低的随机/确定性做法，欢迎与我讨论。
