算法1

(Math+hash) $O(n)$

C++ 代码

#include <iostream>

using namespace std;

const int maxn = 4e4+10;
int a[maxn], b[maxn];
int cnt[maxn];

int main(void) {
    int n, m, z; scanf("%d%d%d",&n,&m,&z);
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    for(int i = 0; i < m; i++) scanf("%d",&b[i]);
    for(int i = 0; i < n; ) {
        while(i < n && a[i] != 1) i++;
        if(i >= n) break;
        int j = i;
        while(i < n && a[i] != 0) i++;
        int len = i-j;
        for(int k = 1; k <= len; k++) cnt[len-k+1] += k;
    }
    // 当前做法复杂度是o(n+m+1的数量)
    // 可以用差分数组来辅助运算，不过复杂度没有优势，是o(2n+2m)
    long long ans = 0;
    for(int i = 0; i < m; ) {
        while(i < m && b[i] != 1) i++;
        if(i >= m) break;
        int j = i;
        while(i < m && b[i] != 0) i++;
        int len = i-j;
        for(int k = 1; k <= len; k++) {
            int x = len-k+1;
            if(z%x == 0 && z/x < maxn) ans += k*cnt[z/x];
        }
    }
    printf("%lld\n", ans);
    return 0;
}

// 长度乘积是k，全为1的2个子数组
// 对其中一个数组，统计不同长度的只包含1的子数组的数量，hash存储
// 对另一个数组，枚举只包含1的子数组，对于每个长度为x的数组，若k%x == 0, ans += map[k/x]