Count Subrectangles

题意翻译

给定长为 $n$ 的数组 $a$ 和长为 $m$ 的数组 $b$，数组中的元素均是 $0$ 或 $1$。有 $n\times m$ 的矩阵 $c$，$c_{i,j}=a_i \cdot b_j$。请求出矩阵 $c$ 面积为 $k$ 的全 $1$ 子矩阵数量。 $1 \leq n,m \leq 40000$，$1 \leq k \leq n \times m$，$0 \leq a_i,b_i \leq 1$。 翻译 by Meatherm

题目描述

You are given an array $ a $ of length $ n $ and array $ b $ of length $ m $ both consisting of only integers $ 0 $ and $ 1 $ . Consider a matrix $ c $ of size $ n \times m $ formed by following rule: $ c_{i, j} = a_i \cdot b_j $ (i.e. $ a_i $ multiplied by $ b_j $ ). It's easy to see that $ c $ consists of only zeroes and ones too. How many subrectangles of size (area) $ k $ consisting only of ones are there in $ c $ ? A subrectangle is an intersection of a consecutive (subsequent) segment of rows and a consecutive (subsequent) segment of columns. I.e. consider four integers $ 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 $ ) a subrectangle $ c[x_1 \dots x_2][y_1 \dots y_2] $ is an intersection of the rows $ x_1, x_1+1, x_1+2, \dots, x_2 $ and the columns $ y_1, y_1+1, y_1+2, \dots, y_2 $ . The size (area) of a subrectangle is the total number of cells in it.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ and $ k $ ( $ 1 \leq n, m \leq 40\,000, 1 \leq k \leq n \cdot m $ ), length of array $ a $ , length of array $ b $ and required size of subrectangles. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i \leq 1 $ ), elements of $ a $ . The third line contains $ m $ integers $ b_1, b_2, \ldots, b_m $ ( $ 0 \leq b_i \leq 1 $ ), elements of $ b $ .

输出格式

Output single integer — the number of subrectangles of $ c $ with size (area) $ k $ consisting only of ones.

输入输出样例

输入样例 #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

说明

In first example matrix $ c $ is: There are $ 4 $ subrectangles of size $ 2 $ consisting of only ones in it: In second example matrix $ c $ is: