B. Count Subrectangles

Link

Solution

完全没思路，看的题解，将k写成p*q的形式，可以发现最终答案与a中长度为p的全1子串和b中长度为q的全1子串有关，于是做a1和b1数组，其中a1[i]为长度为i的全1子串在a中有几个，b1数组同理，最后将满足p*q等于k的a1[p]和b1[q]相乘并累加即可。

Code

int a[maxn], b[maxn];
LL a1[maxn], b1[maxn];

int main() {
    int n, m, k;
    LL ans = 0;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)cin >> a[i];
    for (int i = 0; i < m; i++)cin >> b[i];
    for (int i = 0; i < n; i++) {
        if (!a[i])continue;
        int j = i;
        while (j < n && a[j])j++;
        for (int len = 1; len <= j - i; len++)a1[len] += j - i - len + 1;
        i = j;
    }
    for (int i = 0; i < m; i++) {
        if (!b[i])continue;
        int j = i;
        while (j < m && b[j])j++;
        for (int len = 1; len <= j - i; len++)b1[len] += j - i - len + 1;
        i = j;
    }
    for (int i = 1; i <= n; i++)if (k % i == 0 && k / i <= m)ans += a1[i] * b1[k / i];
    cout << ans << endl;
    return 0;
}