首页 > 代码库 > 【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—向量内积
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。