注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3243][Noi2013]向量内积  

2015-05-18 11:03:00|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3243: [Noi2013]向量内积

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 390  Solved: 59
[Submit][Status][Discuss]

Description

两个d 维向量A=[a1,a2,...,ad]与B=[b1,b2,...,bd]的内积为其相对应维度的权值的乘积和,即:

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

Input

第一行包含3个正整数n,d,k,分别表示向量的个数,维数以及待检测的倍数。 
接下来n行每行有d个非负整数,其中第i行的第j个整数表示向量xi的第j维权值xi,j。

Output

包含两个整数,用空格隔开。
如果存在两个向量xp,xq的内积为k的整数倍,则输出两个向量的编号p与q(要求p<q)。如果存在多组这样的向量组合,输出其中任意一组即可。
若不存在这样的向量组合,则输出两个-1。

Sample Input

3 5 2
1 0 1 0 1
1 1 0 1 0
0 1 0 1 1

Sample Output

2 3

HINT

Solution

K=2的时候,令A=[[a1,a2,...,ad],[b1,b2,...,bd],...,[n1,n2,...,nd]],B=A^T
如果A*B上面除对角线外的元素均为1则无解,否则必定有解
所以运用2396的方法,哪行不为1就把哪行拎出来,暴力判一下就好了。
K=3的话不好想,一定要注意到1^2=2^2(mod 3),于是把原来的d维向量变成d^2维向量,就转换为K=2的问题了。

Code

/**************************************************************
    Problem: 3243
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2044 ms
    Memory:45032 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
char ch,buf[1<<15],*S=buf,*T=buf;
#define getc() (S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 100010
int n,d,m,A[N][110],B[N],C[N],AA[N],flag,pos,id[110][110],cnt,f;
int check(int i,int j){int f=0;
    for(int k=1;k<=d;k++)f+=A[i][k]*A[j][k];
    return f%m==0;
}
#define rep(i,n) for(int i=1;i<=n;i++)
void work2(){
    rep(i,n)rep(j,d)B[j]+=A[i][j];
    rep(i,d)B[i]%=m;
    rep(i,n)rep(j,d)C[i]+=A[i][j]*B[j];
    rep(i,n)C[i]=(C[i]%m-AA[i]+m+m)%m;f=(n-1)%m;
}
void work3(){
    rep(i,d)rep(j,d)id[i][j]=++cnt;
    rep(i,n)rep(j,d)rep(k,d)B[id[j][k]]+=A[i][j]*A[i][k];
    rep(i,cnt)B[i]%=m;
    rep(i,n)rep(j,d)rep(k,d)C[i]+=A[i][j]*A[i][k]*B[id[j][k]];
    rep(i,n)C[i]=(C[i]-AA[i]*AA[i]+m+m)%m;f=(n-1)%m;
}
int main(){
    n=F(),d=F(),m=F();
    rep(i,n)rep(j,d)A[i][j]=F()%m,AA[i]=AA[i]+A[i][j]*A[i][j];
    rep(i,n)AA[i]%=m;
    if(m==2)work2();else work3();
    for(int i=1;i<=n&&!flag;i++)if(f!=C[i])flag=1,pos=i;
    if(flag==0)return puts("-1 -1"),0;
    rep(i,n)if(i!=pos&&check(pos,i)){
        if(pos<i)printf("%d %d\n",pos,i);
        else printf("%d %d\n",i,pos);
        return 0;
    }
}
  评论这张
 
阅读(766)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018