c/c++语言开发共享[NOI2013] 向量内积

注意：c/c++开发分享[NOI2013] 向量内积中的一切数字即数字运算均在(k)的同余系内（即(xleftarrow xbmod k)），*只用于表示向量点积。

暴力的算法是，从小到大枚举向量(a[x])，判定(a[1])到(a[x-1])中是否存在与(a[x])点积为(0)的向量：若存在，暴力搜索答案；否则枚举下一个向量(a[x+1])。

算法的瓶颈在于“判定”这一部分，即计算(sum_{y<x}sigma(a[y]*a[x]not=0))是否等于(x-1)。

当(k=2)时因为(sigma(wnot=0)=w)，所以只需判定下式值为(x-1)即可
[ sum_{y<x}a[x]*a[y]=a[x]*sum_{y<x}a[y] ]
然后是(k=3)的情况，这时因为(sigma(wnot=0)=w^2)，所以只需判定下式值为(x-1)即可
[ sum_{y<x}(a[x]*a[y])^2 =sum_{y<x}(sum_ia[x,i]a[y,i])^2=sum_{y<x}sum_{i}a[x,i]a[y,i]sum_ja[x,j]a[y,j]\ =sum_isum_ja[x,i]a[x,j]sum_{y<x}a[y,i]a[y,j] ]
两种情况的式子都化简到了能快速处理的形式。

#include <bits/stdc++.h> using namespace std;  int n,m,k,id[100001]; int a[100001][101],b[101],c[101][101];  int solve(int x) {     int tot=0;     if(k==2)          for(int i=1; i<=m; b[i]^=a[x][i],i++) tot^=b[i]&a[x][i];     else          for(int i=1; i<=m; ++i)          for(int j=1; j<=m; c[i][j]+=a[x][i]*a[x][j],++j)              tot+=c[i][j]*a[x][i]*a[x][j];     return tot%k; } bool check(int x,int y) {     int tot=0;     for(int i=1; i<=m; ++i) tot+=a[x][i]*a[y][i];     return tot%k==0; }  int main() {     scanf("%d%d%d",&n,&m,&k);     for(int i=1; i<=n; ++i)      for(int j=1; j<=m; ++j)          scanf("%d",&a[i][j]),a[i][j]%=k;     for(int i=1; i<=n; ++i) id[i]=i;     for(int ovo=5; ovo--; ) {         random_shuffle(id+1,id+n+1);         k==2?memset(b,0,sizeof b):memset(c,0,sizeof b);         for(int i=1; i<=n; ++i) if(solve(id[i])!=(i-1)%k)          for(int j=1; j<i; ++j) if(check(id[i],id[j])) {             if(id[i]>id[j]) swap(id[i],id[j]);             printf("%d %dn",id[i],id[j]);             return 0;         }     }     puts("-1 -1");     return 0; }