两个 d 维向量 A=[a1,a2,…,ad] 与 B=[b1,b2,…,bd] 的内积为其相对应维度的权值的乘积和，即：
?A,B?=∑i=1daibi=a1b1+a2b2+?+adbd
现在有 n 个 d 维向量 x1,x2,…,xn ，小喵喵想知道是否存在两个向量的内积为 k 的倍数。请帮助她解决这个问题。
输入格式
第一行包含 3 个正整数 n,d,k ，分别表示向量的个数，维数以及待检测的倍数。
接下来 n 行每行有 d 个非负整数，其中第 i 行的第 j 个整数表示向量 xi 的第 j 维权值 xi,j 。
输出格式
包含两个整数，用空格隔开。
如果存在两个向量 xp,xq 的内积为 k 的整数倍，则输出两个向量的编号 p 与 q （要求 p<q ）。如果存在多组这样的向量组合，输出其中任意一组即可。
若不存在这样的向量组合，则输出两个 ?1 。
样例一
input
3 5 2 1 0 1 0 1 1 1 0 1 0 0 1 0 1 1
output
2 3
explanation
?x1,x2?=1 ， ?x1,x3?=1 ， ?x2,x3?=2 。
限制与约定
| 测试点编号 | n | d | k | xi,j |
|---|---|---|---|---|
| 1 | 2 | 20 | 2 | ≤10 |
| 2 | 5 | 20 | 2 | ≤10 |
| 3 | 10 | 20 | 3 | ≤10 |
| 4 | 20 | 20 | 2 | ≤100 |
| 5 | 50 | 20 | 3 | ≤100 |
| 6 | 50 | 50 | 2 | ≤1000 |
| 7 | 50 | 50 | 3 | ≤3000000 |
| 8 | 80 | 80 | 2 | ≤3000000 |
| 9 | 100 | 100 | 3 | ≤3000000 |
| 10 | 500 | 100 | 3 | ≤3000000 |
| 11 | 1000 | 100 | 2 | ≤3000000 |
| 12 | 1000 | 100 | 3 | ≤3000000 |
| 13 | 10000 | 100 | 2 | <10 |
| 14 | 10000 | 100 | 3 | <10 |
| 15 | 15000 | 100 | 2 | <10 |
| 16 | 18000 | 100 | 2 | <10 |
| 17 | 20000 | 100 | 2 | <10 |
| 18 | 50000 | 30 | 3 | <10 |
| 19 | 80000 | 30 | 3 | <10 |
| 20 | 100000 | 30 | 3 | <10 |
时间限制： 5s
空间限制： 256MB
下载
样例数据下载
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~随机化~
随机大法真是太神辣！！！
发现k==2或3，所以分开来做。
k==2时，我们发现内积只有0或1，所以我们用^运算i与之前的所有的内积是否与(i-1)%mod相等，不相等的话说明前面一定有与i得出的结果是1的，暴力寻找输出即可。
但是显然这样判断的误差非常大，因为这是取模下的运算。所以我们每次随机顺序，然后判断它与之前的序列可不可行，只要判断7-mod次即可。
3的情况同上。
改了半天模数最后发现是id写成了a……
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;int t,n,m,mod,a[100001][101],id[100001],las=1,b[100001],c[101][101];int read()
{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;
}int rand()
{return las=(((long long)las*20000909+2010527)%1000000009)/97;
}int sol(int u)
{int ans=0;if(mod==2) for(int i=1;i<=m;b[i]^=a[u][i],i++) ans^=b[i]&a[u][i];else for(int i=1;i<=m;i++)for(int j=1;j<=m;c[i][j]+=a[u][i]*a[u][j],j++)ans+=c[i][j]*a[u][i]*a[u][j];return ans%mod;
}bool jud(int u,int v)
{int now=0;for(int i=1;i<=m;i++) now+=a[u][i]*a[v][i];return !(now%mod);
}int main()
{n=read();m=read();mod=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) a[i][j]=read()%mod;for(int i=1;i<=n;i++) id[i]=i;t=7-mod;while(t--){for(int i=2;i<=n;i++) swap(id[i],id[rand()%(i-1)+1]);if(mod==2) memset(b,0,sizeof(b));else memset(c,0,sizeof(c));for(int i=1;i<=n;i++)if(sol(id[i])!=(i-1)%mod)for(int j=1;j<i;j++) if(jud(id[i],id[j])){if(id[i]>id[j]) swap(id[i],id[j]);printf("%d %d\n",id[i],id[j]);return 0;}}puts("-1 -1");return 0;
}