神题......

还是大神讲得比较清晰~orz

http://dffxtz.logdown.com/posts/197950-noi2013-vector-inner-product

启发题:poj3318

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#include<bitset>
#include<vector>
#include<functional>
#include<deque>
#include<cctype>
#include<climits>
#include<complex>
//#include<bits/stdc++.h>适用于CF,UOJ,但不适用于poj
#include<ctime> using namespace std; typedef long long LL;
typedef double DB;
typedef pair<int,int> PII;
typedef complex<DB> CP; #define mmst(a,v) memset(a,v,sizeof(a))
#define mmcy(a,b) memcpy(a,b,sizeof(a))
#define re(i,a,b) for(i=a;i<=b;i++)
#define red(i,a,b) for(i=a;i>=b;i--)
#define fi first
#define se second
#define m_p(a,b) make_pair(a,b)
#define SF scanf
#define PF printf
#define two(k) (1<<(k)) template<class T>inline T sqr(T x){return x*x;}
template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}
template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;} const DB EPS=1e-;
inline int sgn(DB x){if(abs(x)<EPS)return ;return(x>)?:-;}
const DB Pi=acos(-1.0); inline int gint()
{
int res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
}
inline LL gll()
{
LL res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
} const int maxN=;
const int maxDD=; int N,DD,D,K;
int v[maxN+][maxDD+]; inline int A1(int i,int j)
{
if(K==)
{
int t1=(j+DD-)/DD,t2=j-(t1-)*DD;
return v[i][t1]*v[i][t2];
}
return v[i][j];
}
inline int A2(int i,int j){return A1(j,i);} int F[maxN+],X[maxN+],GX[maxN+],FX[maxN+],A2X[maxN+],A1A2X[maxN+],TX[maxN+];
inline int work()
{
int i,j,k,Case;
if(1LL*N*D<10000000LL) Case=; else Case=;
while(Case--)
{
re(i,,N)X[i]=rand()%; mmst(GX,);
re(i,,N)GX[]+=X[i];
GX[]%=K;
re(i,,N)GX[i]=GX[]; re(i,,N)FX[i]=F[i]*X[i]; mmst(A2X,);
re(i,,D)re(j,,N)A2X[i]+=A2(i,j)*X[j]; mmst(A1A2X,);
re(i,,N)re(j,,D)A1A2X[i]+=A1(i,j)*A2X[j];
re(i,,N)A1A2X[i]%=K; re(i,,N)
{
TX[i]=GX[i]-FX[i]-A1A2X[i];
TX[i]=(TX[i]%K+K)%K;
if(TX[i]!=)
{
re(j,,N)if(j!=i)
{
int res=;
re(k,,DD)res+=v[i][k]*v[j][k];
if(res%K==){PF("%d %d\n",min(i,j),max(i,j));return ;}
}
}
}
}
return ;
} int main()
{
freopen("meow.in","r",stdin);
freopen("meow.out","w",stdout);
srand(time());
int i,j;
N=gint();D=gint();K=gint();
re(i,,N)re(j,,D)v[i][j]=gint()%K;
DD=D;if(K==)D=D*D;
re(i,,N)
{
F[i]=;
re(j,,D) F[i]+=A1(i,j)*A2(j,i);
F[i]%=K;F[i]^=;
}
if(!work())PF("-1 -1\n");
return ;
}

最新文章

  1. px-rem 一个将px转换为rem的工具
  2. ELK日志系统:Filebeat使用及Kibana如何设置登录认证
  3. ACM: SCU 4438 Censor - KMP
  4. centos 安装 opencv-3.1.0
  5. 与TCP/IP协议的初次见面(一)
  6. thrift之TTransport层的分帧传输类TFramedTransport
  7. IOS 使用SDWebImage实现仿新浪微博照片浏览器
  8. iOS 删除NSString中特定字符
  9. OpenSSH后门获取root密码及防范
  10. PHP几个函数
  11. Codeforces Round #180 (Div. 2) C. Parity Game 数学
  12. [PWA] Enable Push Notification in your web app
  13. Android单元测试Junit (一)
  14. Spring Boot 配置文件详解
  15. golang string和[]byte的对比
  16. Spring再接触 集合注入
  17. (转)Debian 安装与卸载包命令
  18. 【CF809E】Surprise me!(动态规划,虚树,莫比乌斯反演)
  19. Rxjs之创建操作符(Angular环境)
  20. Python2.7-pprint

热门文章

  1. IT项目外包有哪些注意事项
  2. D - Network - poj3694(LCA求桥)
  3. [每日一题] 11gOCP 1z0-053 :2013-09-30 ASMCMD.......................................................8
  4. Fancybox——学习(1)
  5. uploadify不能正确显示中文的按钮文本的解决办法
  6. 苹果推送APNS总结 (
  7. form表单提交之前推断
  8. mac os使用lsusb命令和连接未知的Android设备
  9. NSData的一些用法
  10. fstab的格式