子矩形计数（冬季每日一题 17）

给定一个长度为 $n$ 的数组 $a$ 和一个长度为 $m$ 的数组 $b$。

两个数组均只包含 $0$ 和 $1$。

利用两个给定数组生成一个 $n\times m$ 的矩阵 $c$，其中 $c_{ij}=a_i\times b_j$。

显然，矩阵 $c$ 中也只包含 $0$ 和 $1$。

请问，矩阵 $c$ 中有多少个大小（面积）恰好为 $k$ 且只包含 $1$ 的子矩形？

子矩形是指矩阵中连续若干行和连续若干列的交集。

例如，考虑四个整数 $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,\dots ,x_2$ 和列 $y_1,y_1+1,\dots ,y_2$ 的一个交集。

一个子矩形的大小（面积）等于它包含的数字个数。

输入格式
第一行包含三个整数 $n,m,k$。

第二行包含 $n$ 个整数 $a_1,\dots ,a_n$，表示数组 $a$ 中的元素。

第三行包含 $m$ 个整数 $b_1,\dots ,b_m$，表示数组 $b$ 中的元素。

输出格式
输出满足条件的子矩形的总数量。

数据范围
$1\le n,m\le 40000,$
$1\le k\le n\times m,$
$0\le a_i,b_i\le 1$

输入样例1：

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

输出样例1：

4
1

输入样例2：

3 5 4
1 1 1
1 1 1 1 1
1
2
3

输出样例2：

14
1

样例解释
对于样例 $1$，矩阵 $c$ 如下：

共有 4 个面积为 2 且只包含 1 的子矩形，如下：

对于样例 2，矩形 c 如下：

---

1. 矩形面积为 $k$，可以枚举一个边 $(a,b)$
2. 可以发现求面积为 $k$ 的 $1$ 的矩形个数，相当于求 ($A$ 中有多少个连续的 $1$ 长度为 $a$) ✖ ($B$ 中有多少个连续的 $1$ 长度为 $b$)
3. 用 $s$ 数组距离长度为 $i$ 的 $1$ 的个数，$s[i]$ 表示有 $s[i]$ 个(连续的 $1$)长度为 $i$
4. 当 $A$ 中有连续的 $1$ 长度为 $t$，它对 $s$ 数组 $[1$~$t]$ 都有个为 $1$ 的贡献(相当于给 $s[1$~$t]$ 都加{可以用差分数组处理})

#include

using namespace std;

typedef long long LL;

const int N = 40010;

int n, m, k;
int a[N], b[N];
int s1[N], s2[N];

void work(int w[], int s[], int n){
    
    int j = 0;
    for(int i = 0; i < n; i++)
        if(w[i] == 1){
            j++;
            s[1]++;
            s[j + 1]--;
        }else j = 0;
    
    for(int i = 1; i <= n; i++) s[i] += s[i-1];
}

int main(){
    
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i++) scanf("%d", &b[i]);
    
    work(a, s1, n);
    work(b, s2, m);
    
    LL res = 0;
    for(int i = 1; i <= n; i++){
        
        if(k % i) continue;
        int j = k / i;
        if(j > m) continue;
        
        res += s1[i] * s2[j];
    }
    
    printf("%lld\n", res);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48