题解 P1224 【[NOI2013]向量内积】

· · 题解

NOI2013 向量内积

题目链接

分析

对于前12个数据点我们可以直接暴力枚举。期望分数为60分.下面考虑数据点13~20.

首先，n个d维向量可以组成一个矩阵A=\begin{Bmatrix}\vec a_1\\\vec a_2\\\cdots\\\vec a_n\end{Bmatrix}.那么根据矩阵的性质，有

AA^T=C

,C_{ij}=\vec a_i \vec a^T_j

首先考虑模数为2的情况. 假若A中的向量任二的内积不为0，且C_{ij}=\vec a_i \vec a^T_j \mod 2,那么有

C=E=\begin{Bmatrix}1&\dots &1\\\vdots&\ddots&\vdots\\1&\dots&1\end{Bmatrix}

因而对于k=2的情况，我们只需要观察我们构造的矩阵C中是否存在C_{ij}=0即可.

然而问题在于数据量很大的情况下显然不可能使用O(n^2d)的矩阵乘法.因而我们考虑抽出一部分来进行检验。

首先我们打乱矩阵A中行向量的排列顺序。之后我们求出第i个行向量与前i-1个行向量的内积之和.显然有

\sum\limits_{j=0}^{i-1} \vec a_i \vec a_j^T=\sum\limits_{j=0}^{i-1}\sum\limits_k a_{ik} a_{jk}=\sum\limits_k a_{ik}\sum\limits_{j=0}^{i-1} a_{jk}

如果该行向量与前i-1个行向量的内积对2取余均不为0，那么内积对2取余后求和之值应为i-1.

我们令向量\vec u=[\sum a_{i1} \sum a_{i2} \dots \sum a_{id} ]，那么我们需要求出\vec a_i与\vec u的内积.

在取模意义下，当\vec a_i \cdot \vec u \equiv i-1 \mod 2时，有概率没有向量能与\vec a_i匹配.同时，当\vec a_i \cdot \vec u \not\equiv i-1 \mod 2时，必然存在一个行向量与\vec a_i匹配.此时我们逐一计算内积查找即可.

通过多次随机调整行向量的顺序，我们判定失败的概率就会大大减小.同时由于我们在计算时可以同时更新\vec u，因而总判定的时间复杂度为O(nd).

对于模数为3的情况，我们考虑如何将内积的结果化为01形式（这样方便我们进行判定）。

我们发现，在取模意义下有

$\sum\limits_{j=0}^{i-1} (\vec a_i \vec a_j^T)^2=\sum\limits_{j=0}^{i-1}\sum\limits_x\sum\limits_y a_{ix}a_{jx}a_{iy} a_{jy}=\sum\limits_x\sum\limits_y a_{ix}a_{iy}\sum\limits_{j=0}^{i-1} a_{jx}a_{jy}

我们构造矩阵S=\begin{Bmatrix}\sum a_{i1}a_{i1}&\dots&\sum a_{i1}a_{jd}\\\vdots&\ddots&\vdots\\\sum a_{id}a_{i1}&\dots&\sum a_{id}a_{id}\end{Bmatrix}，逐项对应，做乘法即可.同样我们边乘边更新，时间复杂度为O(nd^2).

（如此巧妙的判定我琢磨了好几个小时）

下面给出代码.其中每个变量的意义与题面及上方所述的变量一一对应.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=101000,maxd=111;
int n,d,k;
int A[maxn][maxd],u[maxd],S[maxd][maxd],id[maxn];
inline int read(){
    int res=0;
    char ch=getchar(),ch1=ch;
    while(!isdigit(ch))ch1=ch,ch=getchar();
    while(isdigit(ch))
        res=(res<<3)+(res<<1)+ch-'0',ch=getchar();
    return ch1=='-'?-res:res;
}
bool check(int x,int y){
    int ans=0;
    for(register int i=1;i<=d;i++)
        ans+=A[x][i]*A[y][i];
    return ans%k;
}
int workadd(int x){
    int ans=0;
    if(k==2)
        for(register int i=1;i<=d;u[i]^=A[x][i],++i)
            ans^=A[x][i]&u[i];//模2时可以用位运算代替乘法与加法
    else
        for(register int i=1;i<=d;++i)
            for(register int j=1;j<=d;S[i][j]+=A[x][i]*A[x][j],++j)
                ans+=A[x][i]*A[x][j]*S[i][j]%k;
    return ans%k;
}
int main()
{
    n=read();d=read();k=read();
    for(register int i=1;i<=n;++i){
        id[i]=i;
        for(register int j=1;j<=d;++j)
            A[i][j]=read()%k;
    }
    for(register int T=0;T<6;++T){
        k==2?memset(u,0,sizeof(u)):memset(S,0,sizeof(S));
        random_shuffle(id+1,id+1+n);//调整行向量顺序
        for(register int i=1;i<=n;++i)
            if(workadd(id[i])!=(i-1)%k)
                for(register int j=1;j<i;++j)
                    if(!check(id[i],id[j])){
                        if(id[i]>id[j])swap(i,j);
                        printf("%d %d\n",id[i],id[j]);
                        return 0;
                    }
    }
    puts("-1 -1");
    return 0;
}