luogu#P1224. [NOI2013] 向量内积

    ID: 5282 远端评测题 1000~5000ms 256MiB 尝试: 48 已通过: 1 难度: 6 上传者: 标签>2013NOI 系列Special Judge矩阵乘法向量

[NOI2013] 向量内积

题目描述

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

$$(A,B)=\sum_{i=1}^d a_ib_i=a_1b_1+a_2b_2+\ldots+a_db_d $$

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

输入格式

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

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

输出格式

包含两个整数,用空格隔开。

如果存在两个向量 xp,xqx_p,x_q 的内积为 kk 的整数倍,则输出两个向量的编号 ppqq(要求 p<qp<q)。如果存在多组这样的向量组合,输出其中任意一组即可。

若不存在这样的向量组合,则输出两个 1-1

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

2 3

提示

数据范围

测试点编号 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 3×106\leq 3\times 10^6
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