#3243. [Noi2013] 向量内积

[Noi2013] 向量内积

题目描述

两个 dd 维向量 A=[a1,a2,...,ad]A=[a_1,a_2,...,a_d]B=[b1,b2,...,bd]B=[b_1,b_2,...,b_d] 的内积为其相对应维度的权值的乘积和,即:

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

输入格式

第一行包含 33 个正整数 n,d,kn,d,k,分别表示向量的个数,维数以及待检测的倍数。

接下来 nn 行每行有 dd 个非负整数,其中第 ii 行的第 jj 个整数表示向量 xix_i 的第 jj 维权值 xi,jx_{i,j}

输出格式

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

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

数据规模与约定

测试点编号 nn dd kk xi,jx_{i,j}
11 22 2020 22 10\leq 10
22 55
33 1010 33
44 2020 22 100\leq 100
55 5050 33
66 5050 22 103\leq 10^{3}
77 33 3×106\leq 3 \times 10^{6}
88 8080 22 2×106\leq 2 \times 10^{6}
99 100100 100100 33 3×106\leq 3 \times 10^{6}
1010 500500
1111 10310^{3} 22 2×106\leq 2 \times 10^{6}
1212 33 3×106\leq 3 \times 10^{6}
1313 10410^{4} 22 <10<10
1414 33
1515 1.5×1041.5 \times 10^{4} 22
1616 1.8×1041.8 \times 10^{4}
1717 2×1042 \times 10^{4}
1818 5×1045 \times 10^{4} 3030 33
1919 8×1048 \times 10^{4}
2020 10510^{5}

题目来源

没有写明来源。

新增数据一组,但未重测。By TA1111,2016.5.17