TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7525
  • 题目
  • P7525[三校联测2] 矩阵
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    14 已经想不出新颖的题目背景了,所以他准备用序列来构造矩阵。

    WY~~(机房巨佬)~~ 给了 14 一个长度为 \(n\) 的序列 \(a\) 和一个长度为 \(m\) 的序列 \(b\)

    14 玩序列玩腻了,准备用这两个序列构造出一个 \(n\times m\) 的矩阵 \(c\)

    14 规定 \(c_{i,j}=a_i\times b_j\),14 是一个好奇的小朋友,他想知道在这个矩阵中有多少个子矩阵的元素之和为 \(k\)

    其中 \(k\) 为 14 给定的一个常数。

    输入格式

    输入第一行包含三个整数 \(n,m,k\),表示序列 \(a\) 的长度,序列 \(b\) 的长度以及 14 给出的常数。

    输入第二行包含 \(n\) 个整数,表示序列 \(a\)

    输入第三行包含 \(m\) 个整数,表示序列 \(b\)

    对于 $100%$ 的数据, $1\le n,m\le 5\times 10^{4}$, $1\le k\le 10^{6}$, $0\le a_i,b_i\le 10^9$。

    测试点编号 \(n,m\) 特殊限制
    $1\sim 2$ \(\le 10\) /
    $3\sim 6$ \(\le 10^2\) /
    $7\sim 10$ \(\le 5\times 10^2\) /
    $11\sim 14$ / $0\le a_i,b_i\le 1$
    $15\sim 16$ / \(k\le 10^3\)
    $17\sim 20$ / /
    输出格式

    输出只有一行,表示符合条件的子矩阵个数。

    样例输入

    3 4 20
    2 3 5
    4 6 3 2

    样例输出

    4

    提示

    构造出的矩阵为

    \[ \begin{pmatrix} 8&12&6&4\\ 12&18&9&6\\ 20&30&15&10 \end{pmatrix} \]

    规定 \((x_1,y_1,x_2,y_2)\) 表示一个左上角为 \((x_1,y_1)\),右下角为 \((x_2,y_2)\) 的子矩阵。

    符合条件的子矩阵有 \((1,1,2,1),(1,1,1,2),(3,3,3,3),(1,4,3,4)\),故答案为 $4$。