题目描述

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

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

利用两个给定数组生成一个 n×m 的矩阵 c，其中 cij=ai×bj。

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

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

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

例如，考虑四个整数 x1,x2,y1,y2(1≤x1≤x2≤n,1≤y1≤y2≤m)，子矩形 c[x1…x2][y1…y2] 即为行 x1,x1+1,…,x2 和列 y1,y1+1,…,y2 的一个交集。

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

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

第二行包含 n 个整数 a1,…,an，表示数组 a 中的元素。

第三行包含 m 个整数 b1,…,bm，表示数组 b 中的元素。

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

数据范围
1≤n,m≤40000,
1≤k≤n×m,
0≤ai,bi≤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

算法1

(差分) $O(n)$

时间复杂度

参考文献

python3 代码

def get_len_freq(nums):
    n = len(nums)
    len_freq = [0 for _ in range(n + 2)]
    curLen = 0
    for i in range(n):
        if nums[i] == 1:
            curLen += 1
            len_freq[1] += 1        #差分，静态区间和
            len_freq[curLen + 1] -= 1
        else:
            curLen = 0
    for i in range(1, n + 1):
        len_freq[i] += len_freq[i-1]
    return len_freq

[an, bn, k] = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

len_freq_a = get_len_freq(a)
len_freq_b = get_len_freq(b)

res = 0
for x in range(1, an + 1):
    if k % x != 0:
        continue
    y = k // x
    if y > bn:
        continue
    res += len_freq_a[x] * len_freq_b[y]
print(res)

C++ 代码

#include<bits/stdc++.h>
using namespace std;

vector<int> get_len_freq(vector<int> & nums)
{
    int n = nums.size();
    vector<int> len_freq(n + 2, 0);
    int curLen = 0;
    for (int i = 0; i < n; i ++)
    {
        if (nums[i] == 1)
        {
            curLen ++;
            len_freq[1] += 1;       //差分
            len_freq[curLen + 1] -= 1;
        }
        else
        {
            curLen = 0;
        }
    }
    for (int i = 1; i < n + 1; i ++)
        len_freq[i] += len_freq[i-1];
    return len_freq;
}

int main()
{
    int an;    cin >> an;
    int bn;    cin >> bn;
    int k;     cin >> k;
    vector<int> a(an);
    for (int i = 0; i < an; i ++)
        cin >> a[i];
    vector<int> b(bn);
    for (int i = 0; i < bn; i ++)
        cin >> b[i];

    vector<int> len_freq_a = get_len_freq(a);
    vector<int> len_freq_b = get_len_freq(b);

    long long res = 0;
    for (int x = 1; x < an + 1; x ++)
    {
        if (k % x != 0)
            continue;
        int y = k / x;
        if (y > bn)
            continue;
        res += (long long)len_freq_a[x] * len_freq_b[y];
    }

    cout << res << endl;

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla