← 返回题目列表

Codeforces · 1323/B

B. 计算子矩形

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和长度为 $$$m$$$ 的数组 $$$b$$$,两者均仅由整数 $$$0$$$ 和 $$$1$$$ 组成。考虑一个大小为 $$$n \times m$$$ 的矩阵 $$$c_{i, j} = a_i \cdot b_j$$$ (即 $$$a_i$$$ 乘以 $$$b_j$$$)。很容易看出 $$$c$$$ 也仅由零和一组成。

$$$c$$$ 中有多少个大小(面积)为 $$$k$$$ 且仅由 1 个组成的子矩形?

子矩形是连续(后续)行段和连续(后续)列段的交集。 IE。考虑四个整数 $$$x_1, x_2, y_1, y_2$$$ ($$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le m$$$) 子矩形 $$$c[x_1 \dots x_2][y_1 \dots y_2]$$$ 是行的交集$$$x_1、x_1+1、x_1+2、\dots、x_2$$$ 和列 $$$y_1、y_1+1、y_1+2、\dots、y_2$$$。

子矩形的大小(面积)是其中的单元格总数。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n, m \leq 40\,000, 1 \leq k \leq n \cdot m$$$)、数组长度 $$$a$$$、数组长度 $$$b$$$ 以及所需的子矩形大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 1$$$),$$$a$$$ 的元素。

第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \leq b_i \leq 1$$$),$$$b$$$ 的元素。

输出

输出单个整数 — $$$c$$$ 的大小(面积)$$$k$$$ 只由 1 组成的子矩形的数量。

示例

输入 #1

3 3 2
1 0 1
1 1 1

输出 #1

4

输入 #2

3 5 4
1 1 1
1 1 1 1 1

输出 #2

14

注意

在第一个示例中,矩阵 $$$c$$$ 是:

有 $$$4$$$ 大小为 $$$2$$$ 的子矩形,其中仅包含以下子矩形:

在第二个示例中,矩阵 $$$c$$$ 为: