#P3243. [Noi2013]向量内积

    ID: 2428 传统题 1000ms 256MiB 尝试: 1746 已通过: 323 难度: 9 上传者: 标签>难度分类省选/NOI-随机化与近似随机赋权检测多次独立采样数论费马小定理构造与建模交换求和顺序枚举与搜索对称性去重计算几何点积CF2600

[Noi2013]向量内积

[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] 的内积等于对应分量乘积之和。

$$\langle A,B\rangle=\sum_{i=1}^{d}a_i b_i=a_1b_1+a_2b_2+\cdots+a_db_d.$$

给定 nn 个 dd 维向量 x1,x2,…,xnx_1,x_2,\ldots,x_n。小喵喵想找出两个不同的向量,使它们的内积是 kk 的倍数。

输入格式

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

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

输出格式

包含两个整数,用空格隔开。如果存在两个向量 xpx_p,xqx_q 的内积为 kk 的整数倍,则输出两个向量的编号 pp 与 qq(要求 p<qp<q)。如果存在多组这样的向量组合,输出其中任意一组即可。若不存在这样的向量组合,则输出两个 −1-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\langle x_1,x_2\rangle=1、⟨x1,x3⟩=1\langle x_1,x_3\rangle=1 和 ⟨x2,x3⟩=2\langle x_2,x_3\rangle=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

这是旧题库另附的示例。

数据规模与约定

测试点编号 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
99 100100 100100 33
1010 500500
1111 10310^{3} 22
1212 33
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}

原赛题面