轩鱼网,宠爱天使官网,平度天气
注意：本文中的一切数字即数字运算均在\(k\)的同余系内（即\(x\leftarrow x\bmod 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(w\not=0)=w\)，所以只需判定下式值为\(x-1\)即可
\[
\sum_{y<x}a[x]*a[y]=a[x]*\sum_{y<x}a[y]
\]
然后是\(k=3\)的情况，这时因为\(\sigma(w\not=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_i\sum_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 %d\n",id[i],id[j]);
return 0;
}
}
puts("-1 -1");
return 0;
}
这一定正确吗？拿衣服 当然不。注意此时的式子实际上是\(\sum\dots\equiv x-1\pmod k\)这样，所以这样判断是存在错判概率的。一个解决办法是把向量顺序打乱多做几次。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论