P1224 [NOI2013]向量内积(矩阵乘法随机化) k=2k=2时
考虑保持前i 1 i-1 i1个向量的前缀和。
求出第II个向量和内积，如果不等于k 1 k-1 k1，则必须满足第i i i项及其内积为00的条件，然后暴力查找即可。
每次特定判断的复杂度为o(d ) o ) d ) o ) d )，只要找到就一定能够在o(d ) o(d ) o ) nd ) nd )的范围内找到。
当k=3 k=3 k=3时，考虑1222(mod3)1(2) equiv2)2) pmod {3} 1222 (mod3)
可以维护c [ i ] [ j ]= j=1 i 1 a j x a
j y large c[i][j]= sumlimits_{j=1}^{i-1} a_{jx}a_{jy} c[i][j]=j=1∑i−1ajxajy因为 ( ∑ k = 1 d a i k a j k ) 2 = ∑ k 1 d ∑ k 2 d a i k 1 a j k 1 a i k 2 a j k 2 large (sumlimits_{k=1}^{d} a_{ik}a_{jk})^2=sumlimits_{k_1}^dsumlimits_{k_2}^da_{ik_1}a_{jk_1}a_{ik_2}a_{jk_2} (k=1∑daikajk)2=k1∑dk2∑daik1ajk1aik2ajk2
所以维护一个 c [ i ] [ j ] c[i][j] c[i][j]的前缀和即可。
每次随机化一下 i d id id，减少失败概率。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ll; const int N=101000,M=111,inf=0x3f3f3f3f,mod=1e9+7;#define mst(a,b) memset(a,b,sizeof a)#define rg registerinline 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;}int a[N][M],b[M],c[M][M];int n,mo,d;inline bool ck(int x,int y){int s=0;for(rg int i=1;i<=d;i++) s+=a[x][i]*a[y][i];return s%mo; }inline int f(int x){int s=0;if(mo==2){for(rg int i=1;i<=d;b[i]^=a[x][i],++i)s^=a[x][i]&b[i];}else {for(rg int i=1;i<=d;i++)for(rg int j=1;j<=d;c[i][j]+=a[x][i]*a[x][j],j++)s+=a[x][i]*a[x][j]*c[i][j]%mo;}return s%mo;}int id[N];int main(){n=read(),d=read(),mo=read();for(rg int i=1;i<=n;++i){id[i]=i;for(rg int j=1;j<=d;++j)a[i][j]=read()%mo;}for(rg int T=0;T<6;T++){mo==2?mst(b,0):mst(c,0);random_shuffle(id+1,id+n+1);for(rg int i=1;i<=n;++i)if(f(id[i])!=(i-1)%mo)for(rg int j=1;j<i;++j){if(!ck(id[i],id[j])){if(id[i]>id[j]) swap(i,j);return printf("%d %dn",id[i],id[j]),0;}}}puts("-1 -1");return 0;}