自动搬运

查看原文

来自洛谷，原作者为

	xzzduang 这个家伙很摆，什么也没有留下

搬运于2025-08-24 21:22:37，当前版本为作者最后更新于2022-07-28 17:18:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

传送门

感谢 wzy 提供的思路，这可能是一个比较数学且困难的做法，和其他题解不太一样。

$k=2$

考虑把这些向量排成一个 $n\times d$ 的矩阵 $A$，考虑把 $A$ 和 $A$ 的转置 $A^T$ 相乘得到 $B$，发现如果有解就是 $B$ 不是一个全 1 矩阵，且如果 $B_{i,j}=0$，答案就是 $i,j$。

思考如何 check 一个全 1 矩阵，随机构造一个 $n$ 行列向量 $R$。如果 $B$ 是一个全 1 矩阵，那么 $B\times R$ 得到的列向量的每个元素都应该是 $R$ 中的所有元素和，且如果第 $i$ 行不满足，那么肯定存在一组 $i,j$ 是答案。

计算 $B\times R$ 也很简单，$B\times R=(A\times(A^T\times R))$，时间复杂度 $\mathcal{O}(nd)$。

$k=3$

因为模 $3$ 意义下 $1$ 和 $2$ 的平方都是 $1$，考虑 check 矩阵 $B$ 的每个值平方后是否是全 1 矩阵，随机生成一个数组 $r[]$，我们要 check 的就是对于每个 $i$，$\sum_jB_{i,j}^2r_j$ 是否等于 $\sum_j r_j$。

考虑构造出矩乘的形式，$\sum_jB_{i,j}^2r_j=\sum_{j}B_{i,j}R_{j,j}B^T_{j,i}$。其中 $R$ 是一个只有对角线有值的矩阵，且 $R_{j,j}=r_j$。现在要 check 的是最终得到的矩阵中对角线的值是否都是 $\sum_j r_j$。如果可以得到最终这个矩阵，构造方案的方法与 $k=2$ 类似。

$$\begin{aligned} &B\times R\times B^T\\ =&A\times (A^T\times (R \times A))\times A^T\\ \end{aligned} $$

其中 $B^T=(A\times A^T)^T=(A^T)^T\times A^T=A\times A^T$。

因为 $R$ 只有对角线有值，所以 $R\times A$ 可以快速处理，中间三项乘出来得时间复杂度是 $\mathcal{O}(nd^2)$。因为我们只关心答案矩阵对角线上的值，左右两个矩阵不用暴力乘上去，考虑答案矩阵的 $Ans_{i,i}$，这时只用取出第一项的第 $i$ 行以及最后一项的第 $i$ 列来乘就好，总的时间复杂度 $\mathcal{O}(nd^2)$。

实现

• 一次随机可能不够，要来多几次。

• 因为模数较小，可以 bitset 优化，所以数据范围可以继续开大。

#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<bitset>
#include<random>
#include<stdlib.h>
using namespace std;
inline int read(){
	int x=0,f=0; char ch=getchar();
	while(!isdigit(ch)) f|=(ch==45),ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
int n,m,k;
struct matrix{
	vector<vector<int> > a;
	int n,m;
	inline void build(){
		a.resize(n+1);
		for(int i=1;i<=n;++i) a[i].resize(m+1);
	}
	matrix operator * (matrix B){
		matrix A=*this,C;
		C.n=A.n,C.m=B.m;
		C.a.resize(C.n+1);
		for(int i=1;i<=C.n;++i) C.a[i].resize(C.m+1);
		for(int i=1;i<=C.n;++i)
			for(int j=1;j<=C.m;++j){
				C.a[i][j]=0;
				for(int k=1;k<=A.m;++k){
					C.a[i][j]+=A.a[i][k]*B.a[k][j];
				}
				C.a[i][j]%=k;
			}
		return C;
	}
};
namespace sub2{
	inline void main(){
		mt19937 rnd(114514);
		matrix A,B;
		A.n=n,A.m=m,A.build();
		B.n=m,B.m=n,B.build();
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				B.a[j][i]=A.a[i][j]=read()%k;
			}
		}
		for(int fick=1;fick<=10;++fick){
			matrix R;
			R.n=n,R.m=1,R.build();
			int sum=0;
			for(int i=1;i<=n;++i) R.a[i][1]=(rnd()&1),(sum+=R.a[i][1])%=2;
			R=B*R;
			R=A*R;
			for(int i=1;i<=n;++i){
				if(R.a[i][1]!=sum){
					for(int j=1;j<=n;++j){
						if(i==j) continue;
						int s=0;
						for(int k=1;k<=m;++k){
							(s+=A.a[i][k]*A.a[j][k])%=2;
						}
						if(s==0){
							printf("%d %d\n",min(i,j),max(i,j));
							return;
						}
					}
				}
			}
		}
		puts("-1 -1");
	}
}
namespace sub3{
	inline void main(){
		mt19937 rnd(114514);
		matrix A,B,C,D;
		A.n=n,A.m=m,A.build();
		B.n=m,B.m=n,B.build();
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				B.a[j][i]=A.a[i][j]=read()%k;
			}
		}
		C=A,D=B;
		for(int fick=1;fick<=10;++fick){
			int sum=0;
			matrix R=C;
			for(int i=1;i<=n;++i){
				int x=rnd()%3;
				(sum+=x)%=3;
				for(int j=1;j<=m;++j){
					(R.a[i][j]*=x)%=3;
				}
			}
			R=B*R;
			for(int i=1;i<=n;++i){
				int s=0;
				for(int j=1;j<=m;++j){
					for(int k=1;k<=m;++k){
						s+=A.a[i][j]*R.a[j][k]*D.a[k][i];
					}
				}
				if(s%3!=sum){
					for(int j=1;j<=n;++j){
						if(i==j) continue;
						int tmp=0;
						for(int k=1;k<=m;++k){
							(tmp+=A.a[i][k]*A.a[j][k])%=3;
						}
						if(tmp==0){
							printf("%d %d\n",min(i,j),max(i,j));
							return;
						}
					}
				}
			}
		}
		puts("-1 -1");
	}
}
int main(){
	n=read(),m=read(),k=read();
	if(k==2) sub2::main();
	else sub3::main();
	return 0;
}