[NOI2013] 向量内积
题目描述
两个 d 维向量 A=[a1,a2,…,ad] 和 B=[b1,b2,…,bd] 的内积等于对应分量乘积之和。
$$\langle A,B\rangle=\sum_{i=1}^{d}a_i b_i=a_1b_1+a_2b_2+\cdots+a_db_d.$$
给定 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。
样例 1
3 5 2
1 0 1 0 1
1 1 0 1 0
0 1 0 1 1
2 3
三个内积分别为 ⟨x1,x2⟩=1、⟨x1,x3⟩=1 和 ⟨x2,x3⟩=2。
样例 2
输入文件 · 输出文件
样例 3
输入文件 · 输出文件
样例 4
2 20 2
0 0 1 1 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1
1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0
1 2
这是旧题库另附的示例。
数据规模与约定
| 测试点编号 |
n |
d |
k |
xi,j |
| 1 |
2 |
20 |
2 |
≤10 |
| 2 |
5 |
| 3 |
10 |
3 |
| 4 |
20 |
2 |
≤100 |
| 5 |
50 |
3 |
| 6 |
50 |
2 |
≤103 |
| 7 |
3 |
≤3×106 |
| 8 |
80 |
2 |
| 9 |
100 |
100 |
3 |
| 10 |
500 |
| 11 |
103 |
2 |
| 12 |
3 |
| 13 |
104 |
2 |
<10 |
| 14 |
3 |
| 15 |
1.5×104 |
2 |
| 16 |
1.8×104 |
| 17 |
2×104 |
| 18 |
5×104 |
30 |
3 |
| 19 |
8×104 |
| 20 |
105 |
原赛题面