注意: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; }
-
这一定正确吗?
拿衣服当然不。注意此时的式子实际上是(sumdotsequiv x-1pmod k)这样,所以这样判断是存在错判概率的。一个解决办法是把向量顺序打乱多做几次。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603441.html