夏晓光(loveJY)的博客

NOI2013D1T1?

两个 ddd 维向量 $A=[a_1,a_2,\ldots,a_d]$ 与$B=[b_1,b_2,\ldots,b_d]$的内积为其相对应维度的权值的乘积和，即：

$(A,B)=\sum_{i=1}^d a_ib_i=a_1b_1+a_2b_2+\ldots+a_db_d$

现有 $n$ 个 $d$维向量 $x_1,\ldots,x_n$小喵喵想知道是否存在两个向量的内积为$k$的倍数。请帮助她解决这个问题。

$k<=3$

这个k<=3就很棒,直接蒙圈的那种

首先不难发现我们有随机化做法,就是打乱然后$N^2$的那种,他人实测只有70...

100pts做法,不一定是正解啊

我们考虑k=2的时候,可以把他们前i-1个向量用和压成一个向量

然后用第i个向量去乘,如果和前面每个向量乘积都为1那么和就是(i-1)&1,否则一定有一个向量和他的乘积不是1,就是2的倍数了,这个可以暴力找

具体只需要维护d个位置前缀和就行了

当k=3时,这个乘积不为0就是2或1,但2或1都可以平方一次之后%3=1

那么我们只需要维护d个位置前缀平方和就行了,复杂度是$O(nd^2)$

这样仍然变成了1和之前一样了

然而傻子也能发现可能会出现找不到解的情况,也就是同时有两个都乘积不为1

那么这样我们只需要random_shuffle一下重来就行了

具体实现时和矩阵乘法差不多

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e5+7;
const int MAXM=107;
int n,m,mo,rand_now=MAXN*10,a[MAXN][MAXM],c[MAXN][MAXM],q[MAXN];
int id[MAXN],b[MAXM];

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
	inline char nc() {
		if(p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x=0,f=1;
		char s=nc();
		for(; !isdigit(s); s=nc())if(s=='-')f=-1;
		for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
		return x*f;
	}
}
using namespace fastIO;

bool check(int x,int y) {
	int tmp=0;
	for(int i=1; i<=m; ++i)tmp+=a[x][i]*a[y][i];
	//检查是否为0
	return (tmp%mo==0);
}

inline int solve(int x) {
	int ans=0;
	if(mo==2)for(int i=1; i<=m; b[i]^=a[x][i],++i)ans^=b[i]&a[x][i];
	//异或相当于加了之后取模
	//and一下,就相当于乘积 
	else {
		for(int i=1; i<=m; ++i) {
			for(int j=1; j<=m; c[i][j]+=a[x][i]*a[x][j],++j)ans+=c[i][j]*a[x][i]*a[x][j];
            //这个平方和其实是个n^2矩阵?
		}
	}
	return ans%mo;
}

int main() {
//	freopen("test.in","r",stdin);
	n=read();
	m=read();
	mo=read();
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j)a[i][j]=read()%mo;
	}
	for(int i=1; i<=n; ++i)id[i]=i;
	for(int eps=1; eps<=6; ++eps) {
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		random_shuffle(id+1,id+n+1);
		for(int i=1; i<=n; ++i) {
			if(solve(id[i])!=(i-1)%mo) {
				for(int j=1; j<i; ++j) {
					if(check(id[i],id[j])) {
						if(id[i]>id[j])swap(i,j);
						printf("%d %d\n",id[i],id[j]);
						return 0;
					}
				}
			}
		}
	}
	puts("-1 -1");
	return 0;
}