首页 > 代码库 > 【uoj121】 NOI2013—向量内积

【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;}

 

【uoj121】 NOI2013—向量内积