【uoj121】 NOI2013—向量内积

时间：2023-03-08 19:29:19
【uoj121】 NOI2013—向量内积

http://uoj.ac/problem/121 (题目链接)

题意

　　给出${n}$个${d}$维向量，问是否有两个不同的向量的内积是${k}$的倍数。

Solution

　　又卡了一上午常数，我弃了T_T。

　　右转题解→_→：llg

代码

// uoj121

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<ctime>

#define RG register

#define LL long long

#define inf (1ll<<30)

#define MOD 1000000007

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

inline int gi() {

	int x=0,f=1;char ch=getchar();

	while (ch<'0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();}

	while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

const int maxn=100010,maxd=110;

int a[maxn][maxd],l[maxn],r[maxn];

int u[maxn],v[maxn],p[maxn],tmp[maxn];

int n,d,K,tt;

inline void inc(int &x,RG int y) {

	x+=y;while (x>=K) x-=K;

}

inline int Z(RG int i,RG int j) {

	if (K==2) return a[i][j];

	RG int w=a[i][l[j]]*a[i][r[j]];

	return w>=K ? w-K : w;

}

inline bool solve() {

	for (RG int i=1;i<=n;++i) v[i]=rand()%K,u[i]=v[i],tmp[i]=0;

	int sum=0,c=0;

	for (RG int i=1;i<=n;i++) inc(sum,v[i]);

	for (RG int i=1;i<=n;i++) {

		int t=sum-1*v[i]+p[i]*v[i]+K;

		v[i]=0,inc(v[i],t);

	}

	for (RG int i=1;i<=d;i++)

		for (RG int j=1;j<=n;j++) inc(tmp[i],u[j]*Z(j,i));

	if ((double)clock()/CLOCKS_PER_SEC>=4.5) return 0;

	for (RG int i=1;i<=d;i++) u[i]=tmp[i],tmp[i]=0;

	for (RG int i=1;i<=n;i++) {

		for (RG int j=1;j<=d;j++) inc(tmp[i],u[j]*Z(i,j));

		if (tmp[i]!=v[i]) {c=i;break;}

	}

	if (!c) return 0;

	for (RG int i=1;i<=n;i++) if (i!=c) {

			RG int q=0;

			for (RG int j=1;j<=tt;j++) inc(q,a[i][j]*a[c][j]);

			if (!q) {

				printf("%d %d\n",min(i,c),max(i,c));

				return 1;

			}

		}

	return 1;

}

int main() {

	srand(time(NULL));

	n=gi(),d=gi(),K=gi();

	for (RG int i=1;i<=n;i++)

		for (RG int j=1;j<=d;j++) a[i][j]=gi()%K;

	tt=d;

	if (K==3) {

		d*=d;

		for (RG int i=1;i<=d;i++) l[i]=(i-1)%tt+1,r[i]=(i-l[i])/tt+1;

	}

	for (RG int i=1;i<=n;i++) {

		for (RG int j=1;j<=tt;j++) inc(p[i],a[i][j]);

		if (K==3) (p[i]*=p[i])%=K;

	}

	RG int T=5,flag=0;

	while (T--) {

		flag=solve();

		if (flag) break;

	}

	if (!flag) puts("-1 -1");

	//printf("%.3lf",(double)clock()/CLOCKS_PER_SEC);

	return 0;

}

相关文章