Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

You are given an array a of length n and array b of length m both consisting of only…

  1. User

    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 × m formed by following rule: c_{i, j} = a_i ⋅ 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 ≤ x_1 ≤ x_2 ≤ n, 1 ≤ y_1 ≤ y_2 ≤ m) a subrectangle c[x_1 ... x_2][y_1 ... y_2] is an intersection of the rows x_1, x_1+1, x_1+2, ..., x_2 and the columns y_1, y_1+1, y_1+2, ..., y_2.

    The size (area) of a subrectangle is the total number of cells in it. Input

    The first line contains three integers n, m and k (1 ≤ n, m ≤ 40 000, 1 ≤ k ≤ n ⋅ m), length of array a, length of array b and required size of subrectangles.

    The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 1), elements of a.

    The third line contains m integers b_1, b_2, …, b_m (0 ≤ b_i ≤ 1), elements of b.

    Output

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

    Examples

    Input

    3 3 2 1 0 1 1 1 1

    Output

    4

    Input

    3 5 4 1 1 1 1 1 1 1 1

    Output

    14

    Note

    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:

  2. DeepSeek Assistant

    We are given two binary arrays a (length n) and b (length m). We form matrix c of size n x m with c[i][j] = a_i * b_j. So the matrix is the outer product of a and b: it has ones only where both a_i=1 and b_j=1. Thus the matrix has rows that are either all zeros (if a_i=0) or a copy of the row vector b (if a_i=1). Similarly, columns are either zeros or a. Actually if a_i=1, then row i is exactly b; if b_j=1, then column j is exactly a. So the matrix c is essentially a block of ones where rows corresponding to ones in a and columns corresponding to ones in b are all ones, and elsewhere zeros. In other words, the ones form a rectangle (in the sense of Cartesian product) of dimensions A x B where A = number of ones in a, B = number of ones in b. But careful: if we take all rows i where a_i=1 and all columns j where b_j=1, those cells are ones. But the matrix also includes rows with a_i=0, where all entries are zero, and columns with b_j=0 where all entries are zero. So the matrix is not exactly a contiguous block; it is a submatrix formed by selecting rows with ones and columns with ones. But note: the positions of ones are not necessarily contiguous; they are scattered according to the positions of ones in a and b. However the pattern is that c[i][j] = 1 if and only if a_i=1 and b_j=1. So the ones lie at the intersection of rows where a_i=1 and columns where b_j=1. So if we list the indices of rows with a_i=1 as r_1, r_2, ..., r_A (in increasing order), and columns with b_j=1 as c_1, c_2, ..., c_B (in increasing order), then the ones are at all pairs (r_i, c_j). So the matrix of ones is like a "grid" formed by these row and column positions.

    Now we need to count the number of subrectangles (contiguous blocks of rows and columns) of size (area) exactly k that consist entirely of ones. A subrectangle is defined by a contiguous range of rows [x1, x2] and contiguous range of columns [y1, y2], and its area is (x2 - x1 + 1) * (y2 - y1 + 1) = k. The condition that the subrectangle consists only of ones means that for every row i in that range and column j in that range, c[i][j] must be 1. In other words, the subrectangle must be fully contained within the ones. That means: for all i in [x1, x2], a_i must be 1; and for all j in [y1, y2], b_j must be 1. Because if any a_i=0, then entire row i is zeros, so the subrectangle would have zeros; similarly for b_j=0. So the subrectangle must be chosen such that the row interval contains only rows where a_i=1, and the column interval contains only columns where b_j=1.

    Thus the problem reduces to: Given binary string a of length n, and binary string b of length m, count the number of pairs (row interval, column interval) such that:

    • The row interval [l, r] (1-indexed) is contiguous, and for all i in [l, r], a_i = 1.
    • The column interval [u, v] is contiguous, and for all j in [u, v], b_j = 1.
    • The area (r - l + 1) * (v - u + 1) = k.

    Since the rows and columns are independent (the condition factorizes), we can count for each possible row length L (number of rows in the interval) such that there exists a contiguous segment of rows of length L where all a_i=1, and similarly for column length W such that there exists a contiguous segment of columns of length W where all b_j=1, and L * W = k. But careful: The row interval must be contiguous and consist entirely of ones, but there might be many different intervals of that length. For each L, we need the number of contiguous intervals of rows of length L that are all ones. Let's denote f(L) = number of contiguous subarrays of a of length L that consist entirely of ones. Similarly g(W) = number of contiguous subarrays of b of length W that consist entirely of ones. Then the total number of subrectangles of area k consisting only of ones would be sum_{L * W = k} f(L) * g(W). However, is this correct? Let's check: For a given row interval of length L and column interval of length W, the subrectangle defined by them has area LW. Since both intervals consist of all ones, the subrectangle will contain only ones. And any subrectangle of ones must have that property. And each subrectangle is uniquely determined by its row interval and column interval. So indeed total = sum_{LW = k} f(L) * g(W). But wait, there is a subtlety: Could there be subrectangles of ones that are not product of a row-all-ones interval and column-all-ones interval? Because suppose the row interval includes a row with a_i=0? Then that row would contain zeros in some columns, but maybe if we restrict columns to those where b_j=0? No, because then c[i][j] = a_i * b_j = 0 if either is 0. So for a cell to be 1, both must be 1. So if any row has a_i=0, then for all columns j, c[i][j]=0, so the subrectangle would contain that row, and all cells in that row would be 0, violating the all-ones condition. So indeed the row interval must consist only of rows with a_i=1. Similarly, column interval must consist only of columns with b_j=1. So factorization holds.

    Thus the problem reduces to computing for a and b the counts of contiguous all-ones segments of each possible length, then summing over factor pairs of k.

    But n,m up to 40000, k up to nm (which could be 1.6e9). However we only need lengths up to n and m, and k may be huge. But we are summing over factor pairs LW=k, with L ≤ n and W ≤ m, so only factors of k that are within these bounds matter. Since n,m ≤ 40000, we can compute f(L) for L=1..n, but n can be 40000, which is fine. Similarly g(W) up to 40000. So we can precompute f array and g array of size up to 40000. Then iterate over all L from 1 to n such that L divides k and k/L ≤ m, and add f(L)*g(k/L). That is O(n + m + number of divisors). Since n,m up to 40000, that's fine.

    But wait: f(L) is the number of contiguous subarrays of a of length L that are all ones. Similarly for g. We need to compute these efficiently. Since a is binary, we can compute the lengths of contiguous blocks of ones. For each block of ones of length len, it contributes to f(L) for each L from 1 to len: number of subarrays of length L within that block is (len - L + 1). So if we have the lengths of all maximal contiguous segments of ones, we can compute f(L) by summing over blocks: f(L) = sum_{each block of length len} max(0, len - L + 1). So we can compute f for all L by iterating over blocks and adding contributions. Since total sum of lengths of blocks ≤ n, we could do O(n) by for each block, for L=1 to len add 1? That would be O(total length) = O(n), but if we do for each block, and for each L from 1 to len increment f[L] by 1? Actually we need to add (len - L + 1) for each L. So if we iterate L from 1 to len, we add (len - L + 1). That would be O(len) per block, total O(n). Since n ≤ 40000, that's fine even O(n^2) would be 1.6e9 too high, but O(n) is fine. Actually total sum of len over blocks = n, so iterating each block and for each L from 1 to len, we can add contributions to f[L]. That is O(total length) = O(n). But careful: For each L we need to add (len - L + 1). If we do a double loop (block, L from 1 to len), that's sum of len over all blocks = total number of ones? Actually total number of ones positions in a is at most n, but the length of a block is len, and the number of L values is len, so for each block the inner loop runs len times. So total over all blocks is sum(len) = total number of ones? Wait, sum(len) over blocks is the total number of ones, which could be as high as n. So total inner iterations is O(n). So that's O(n). So we can compute f[L] by initializing an array of size n+1 to 0, then for each block length len, for L=1 to len: f[L] += len - L + 1. That's O(n). Similarly for b O(m). But we need to be careful: n,m up to 40000, O(n) is fine.

    Alternatively, we could compute all possible contiguous ones intervals counts more efficiently via convolution or something, but not needed.

    Thus solution: parse input, compute arrays ones lengths for a and b.

    But there is a nuance: k can be up to n*m (1.6e9) which is large, but we only consider divisors L such that L ≤ n and W = k/L ≤ m. Since n,m ≤ 40000, the number of such divisors is limited because L must be ≤ 40000. We can just iterate L from 1 to n, check if k % L == 0 and W = k/L ≤ m, then add f[L] * g[W]. That is O(n) which is up to 40000, fine.

    But we must ensure that the multiplication f[L] * g[W] fits in 64-bit. The answer could be up to number of subrectangles: f[L] up to number of subarrays of a of length L; maximum possible f[L] when a is all ones: then f[L] = n - L + 1. Similarly g[W] = m - W + 1. So maximum product for LW = k, say L≈sqrt(k) but limited by n,m. The total number of subrectangles of area k overall could be huge? For all-ones matrix, the total number of subrectangles of area exactly k is something like: number of divisors of k and sums over L, each product (n-L+1)(m - k/L + 1). For n,m up to 40000, maximum n and m are 40000 each, so worst-case n=40000, m=40000, k=1.6e9, but L and W would be factors. The maximum (n-L+1) could be up to 40000, similarly (m-W+1) up to 40000, product up to 1.6e9. Summed over divisors, maybe a few tens, so total up to maybe ~1e10, still fits in 64-bit (2^63-1 about 9e18). So we can use 64-bit integer.

    Thus the solution seems straightforward.

    But wait: The problem statement says "subrectangles of size (area) k consisting only of ones". And we derived that the subrectangle must have row interval all ones in a and column interval all ones in b. However, is it possible that the subrectangle consists only of ones but the row interval includes a row with a_i=0, but that row's entries in the selected column interval might all be ones because those columns have b_j=0? No, because c[i][j] = a_i * b_j: if a_i=0, then regardless of b_j, product is 0. So any cell with a_i=0 is 0. So the row would have zeros everywhere. So if the row interval includes a row with a_i=0, then that row in the subrectangle contains all zeros, so subrectangle cannot consist only of ones. So indeed row interval must be all ones in a. Similarly columns.

    Thus factorization is correct.

    Hence algorithm:

    1. Read n,m,k.
    2. Read array a of length n.
    3. Read array b of length m.
    4. Compute f array (size n+1, index length L) for a:
      • Traverse a to find all maximal contiguous segments of ones.
      • For each segment length len: for L = 1 to len: f[L] += (len - L + 1). This is O(n). Use long long for f.
    5. Compute g similarly for b, size m+1.
    6. Initialize answer = 0 (64-bit).
    7. For L = 1 to n: if k % L == 0: W = k / L; if W <= m: answer += f[L] * g[W];
    8. Print answer.

    Check with examples.

    Example1: n=3,m=3,k=2 a = [1,0,1] b = [1,1,1] Compute a blocks: lengths: block at position1 len1? Actually a: indices:1:1,2:0,3:1 => two blocks: length1 at row1, length1 at row3. So for len=1: contributions: for L=1: f[1] += (1-1+1)=1. So f[1]=2. f[2] and f[3] are 0. b = all ones => one block of length3. So g[1] = (3-1+1)=3; g[2]= (3-2+1)=2; g[3]= (3-3+1)=1. Now for L=1, k%1==0, W=2, W<=3? Yes, answer += f[1]g[2]=22=4. L=2: k%2=0, W=1, answer += f[2]g[1]=03=0. L=3: k%3=2 -> not divisible. So total=4. Matches example.

    Example2: n=3,m=5,k=4 a = [1,1,1] (all ones) => one block length3 => f[1]=3, f[2]=2, f[3]=1. b = [1,1,1,1,1] (all ones) => block length5 => g[1]=5, g[2]=4, g[3]=3, g[4]=2, g[5]=1. Now L from 1 to 3: L=1: k%1=0, W=4, W<=5? yes, answer+=f[1]g[4]=32=6. L=2: k%2=0, W=2, answer+=f[2]g[2]=24=8. L=3: k%3? 4%3=1 not divisible. Total=14. Matches.

    So solution works.

    But we must consider that f and g arrays are defined only up to n and m. L and W should be positive integers. So L from 1..n inclusive.

    Now note that k can be large, but we only consider L up to n. So complexity O(n + m). Good.

    But careful: If k is huge and n,m small, the number of valid L may be small. Our loop from 1 to n is fine (max 40000). So that's okay.

    Potential pitfalls: Need to handle when k is 0? But constraint says k >= 1. So fine.

    Edge cases: If there are no ones in a or b, then f[L] all zero, answer zero. Works.

    One nuance: Our computation of f[L] via iterating over each block and for L=1..len adding len-L+1 works O(total ones) but careful: f array length is n+1, we might exceed memory if we allocate n+1 for each? n=40000, fine.

    Alternatively, we could compute f using a frequency array of segment lengths, but our method is fine.

    But we should be mindful: For each block of length len, we add to f[L] for L from 1 to len. If we do that naively, it's O(len). Since sum len <= n, total O(n). However, we need to allocate f as possibly a vector of long long of size n+1, initialize to 0. Then for each len, for L=1..len: f[L] += len - L + 1. That is okay.

    Potential optimization: Could compute f via cumulative method: For each len, the contributions are an arithmetic sequence: for L=1: len, L=2: len-1, ..., L=len:1. So we could do difference arrays: For each segment, we add +1 to f[1]..f[len] with decreasing? Actually it's like f[L] gets + (len - L + 1). That can be computed by two difference arrays: Represent f[L] as sum over segments of (len+1) * 1_{L ≤ len} - L * 1_{L ≤ len}. But easier is to just loop over L.

    Given n up to 40000, total inner loops up to 40000, that's trivial.

    But wait: Sum of len over all blocks is number of ones? Actually a block of length len contains len ones. So sum of len = total number of ones in a. That could be as high as n = 40000. So total inner iterations is 40000. So fine.

    Similarly for b.

    Thus solution is efficient.

    But we should double-check if there's any nuance about subrectangles being defined by row and column intervals, and the condition that the subrectangle consists only of ones might be satisfied even if some row in the interval has a_i=0 but all columns in the interval have b_j=0? Because if b_j=0 then c[i][j]=0 anyway. So row with a_i=0 yields zeros for all columns. For the subrectangle to have only ones, every cell must be 1. So if a_i=0, the row is all zeros; cannot be all ones. So not possible.

    Similarly column.

    Thus factorization stands.

    Now there is another nuance: Could there be a subrectangle that is not product of a row-all-ones interval and column-all-ones interval, but still all ones? Suppose a_i=0 for some i, but the column interval might exclude all columns where b_j=1? But even if b_j=0, c[i][j] = 0. So still zero. So not possible.

    Thus solution is correct.

    Now implement.

    Implementation details:

    • Use 0-indexed arrays for input.
    • Compute blocks lengths: iterate through array, count consecutive ones.
    • For each block length len, for L=1..len: f[L] += len - L + 1.
    • For b similarly.

    We must ensure f and g indices start at 1. So allocate vectors of size max(n,m)+2.

    Potential overflow: f[L] * g[W] could be up to around (n)*(m) ~ 1.6e9, which fits in 64-bit. But sum might be up to maybe 1e12, still fits.

    Now code in C++:

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n, m;
        ll k; // but k may be up to 1.6e9, fits 32-bit, but we need to compute k/L, so use 64-bit
        cin >> n >> m >> k;
        vector<int> a(n), b(m);
        for (int i=0;i<n;++i) cin>>a[i];
        for (int i=0;i<m;++i) cin>>b[i];
    
        vector<ll> f(n+1,0), g(m+1,0); // f[L] count for rows length L
    
        // compute f
        int i=0;
        while (i<n) {
            if (a[i]==0) { i++; continue; }
            int start = i;
            while (i<n && a[i]==1) i++;
            int len = i - start;
            for (int L=1; L<=len; ++L) {
                f[L] += (len - L + 1);
            }
        }
    
        // compute g similarly
        i=0;
        while (i<m) {
            if (b[i]==0) { i++; continue; }
            int start = i;
            while (i<m && b[i]==1) i++;
            int len = i - start;
            for (int L=1; L<=len; ++L) {
                g[L] += (len - L + 1);
            }
        }
    
        ll ans = 0;
        for (int L=1; L<=n; ++L) {
            if (k % L == 0) {
                ll W = k / L;
                if (W <= m) {
                    ans += f[L] * g[W];
                }
            }
        }
        cout << ans << '\n';
        return 0;
    }
    

    But check: we used L as int, but k may be up to 1.6e9, L up to 40000, k/L fits in 64-bit, but we need to ensure k/L integer.

    Edge case: k/L may overflow? No, k up to 1.6e9, L >=1, so <=1.6e9 fits in 32-bit, but we store in ll.

    That's fine.

    Time complexity: O(n + m + min(n,m) maybe plus loops for blocks). The inner loops for each block sum to total ones count, which is at most n and m. So overall O(n+m). Good.

    But wait: There is a nuance: The f[L] values may be zero for many L, but we still iterate L up to n. That's okay.

    Now confirm with some custom tests.

    Test1: n=1,m=1,k=1, a=[1],b=[1]. a block len=1 => f[1]=1. b block len=1 => g[1]=1. L=1, k%1=0, W=1<=1, ans=1. Output 1. Good.

    Test2: n=1,m=1,k=1, a=[0],b=[1]. a has no ones => f[1]=0 => ans=0. Good.

    Test3: n=2,m=3,k=6 (max area). a=[1,1], b=[1,1,1] => f[1]=2, f[2]=1; g[1]=3,g[2]=2,g[3]=1. L=1, W=6? k%1=0, W=6, but 6>3 => ignore. L=2, W=3, W<=3 => ans += f[2]g[3]=11=1. So answer=1. That corresponds to the whole matrix (2x3) which is area 6, all ones, so only one subrectangle. Good.

    Test4: n=2,m=3,k=4. a all ones, b all ones. f[1]=2,f[2]=1. g[1]=3,g[2]=2,g[3]=1. L=1: W=4 >3 ignore. L=2: W=2 => f[2]g[2]=12=2. So answer 2. Which are? Row interval of length2 (only the whole rows), column intervals of length2: there are 2 such intervals: columns (1,2) and (2,3). So indeed 2 subrectangles. Good.

    Test5: More complex pattern: a=[1,1,0,1,1], n=5. So blocks: lengths 2 and 2? Actually positions: 1,2 are ones => block len2; then index3 zero; then indices4,5 ones => block len2. So f[1] = from first block: (2-1+1)=2, from second:2 => total 4. f[2] = from first: (2-2+1)=1, from second:1 => total2. f[3]=0. b similarly.

    Now check some random.

    Thus solution is correct.

    But wait, the problem might be trickier: The matrix c has zeros and ones; subrectangles consisting only of ones might also be found even if the row interval includes zeros in a but the column interval is such that those rows have zeros only in columns where b_j=0? Actually we argued no because any cell with a_i=0 yields 0. So indeed.

    Thus solution stands.

    Now final answer: Provide code and explanation.

    But before finalizing, let's double-check the constraints: n,m ≤ 40000. k can be up to n*m, which is up to 1.6e9. L from 1 to n is 40000. So loop is fine. The f and g arrays of length up to 40000, fine.

    One more nuance: The sum of len for a might be up to n but len can be up to n. The inner loop for each len does L from 1 to len, which is O(len). So total O(n). So all good.

    But consider if a has a block of length 40000. Then the inner loop iterates 40000 times, fine.

    Thus solution passes.

    I'll produce final answer.

    But wait: There's also possibility that the subrectangle could be "empty"? No, area k ≥ 1.

    Now produce final solution.

    But before writing final answer, consider alternative approach: Might there be subrectangles that are not product of a contiguous all-ones rows and columns? Actually, think: Suppose a has pattern: [1,0,1], b = [1,0,1]. Then the ones are at positions (1,1), (1,3), (3,1), (3,3). Could there be a subrectangle consisting of rows 1-3 and columns 1-3? That includes zeros, so not all ones. Could there be subrectangle rows 1-1, columns 1-3? That includes column2 where b2=0, so (1,2)=0. So no. Could there be subrectangle rows 1-3 and columns 1-1? That includes row2 where a2=0, so (2,1)=0. So no. So only subrectangles are product of row intervals fully inside rows with a_i=1 and column intervals fully inside columns with b_j=1. But what about row interval 1-1 and column interval 1-1? That is a single cell (1,1) which is one. Good. Row interval 1-1 and column interval 3-3 also one. Row interval 3-3 and column interval 1-1 also one. Row interval 3-3 and column interval 3-3 also one. So that's 4 subrectangles of area 1. So factorization: f[1]=2, g[1]=2 => product 4. Works.

    Now, consider a case where a has block of ones not contiguous? Actually blocks are contiguous by definition. The condition for row interval to be all ones means the interval must be a subinterval of a contiguous block of ones. Because if interval includes a zero, it fails. So indeed each valid row interval corresponds to a contiguous subsegment of a block of ones. So the count f[L] is exactly the sum over blocks of max(0, len - L + 1). So our computation is correct.

    Thus final answer is correct.

    Now possible pitfalls: I used int for L, len, etc. but need to avoid overflow when computing f[L] increment. For len up to 40000, len-L+1 up to 40000, and we sum across blocks, total f[L] up to about 4000040000? Actually worst-case if many blocks? The maximum f[L] occurs when a is all ones: then f[L] = n - L + 1, which is at most 40000. Actually if a is all ones, there is one block of length n, so f[L] = n - L + 1 <= n. If there are many blocks, say alternating 1,0,1,0,... then number of blocks about n/2, each block length 1, then f[1] = number of blocks = n/2, f[2]=0, etc. So f[L] ≤ n. Actually f[L] is at most n because each row can be part of at most one interval of length L? Wait, for a given L, the number of intervals of length L that are all ones is at most n-L+1, which is ≤ n. So f[L] ≤ n. Similarly g[W] ≤ m. So product ≤ nm ≤ 1.6e9, but n,m up to 40000, product up to 1.6e9. However sum of products over divisors might be larger? At most about (number of divisors of k) * 1.6e9, but number of divisors of a number ≤ 1.6e9 is at most maybe around 1344 (max for numbers under 2e9), but typically less. So answer ≤ 2e12, still fits in 64-bit.

    Thus safe.

    Now we can finalize.

    But what about time? O(n+m) is fine.

    Now final answer.

    But I think there is an alternative: Could there be any subrectangles that are not aligned with rows/columns? No, subrectangle is always axis-aligned.

    Thus final code as above.

    Now I will produce final solution explanation in the required format.

    But the user asked: "You are given ... How many subrectangles ...?" and I need to output answer. I'll provide the solution.

    But check: The problem may be from Codeforces (maybe problem "Subrectangles" or something). In Codeforces, there might be twist: k up to 1e9, n,m up to 40000. Our solution is correct.

    I will produce final answer: algorithm description and C++ code.

    Now final. The matrix (c) is defined by (c_{i,j} = a_i \cdot b_j). A subrectangle consists only of ones exactly when its rows are a contiguous interval of indices with (a_i = 1) and its columns are a contiguous interval with (b_j = 1). Therefore, the problem reduces to counting pairs of intervals (row interval, column interval) such that:

    • The row interval has length (L) and lies completely inside a block of consecutive ones in (a).
    • The column interval has length (W) and lies completely inside a block of consecutive ones in (b).
    • (L \cdot W = k).

    Let (f(L)) be the number of contiguous row intervals of length (L) that contain only ones (i.e., the number of length-(L) subarrays of (a) consisting entirely of 1). Define (g(W)) similarly for (b). Then the answer is

    [ \sum_{L=1}^{n} [k \bmod L = 0 \text{ and } W = k/L \le m] ; f(L) \cdot g(W). ]

    To compute (f) and (g) efficiently, we extract all maximal blocks of consecutive ones in (a) and (b). For a block of length (\ell), it contributes (\ell - L + 1) row intervals of length (L) (for (L = 1,\dots,\ell)). Summing over all blocks gives (f(L)). The same is done for (g).

    The lengths (n,m \le 40000), so we can compute (f) and (g) in (O(n+m)) by iterating over each block and adding the contributions for every possible (L) within that block. Then we iterate (L = 1 \dots n) and add the product whenever the corresponding (W) is valid.

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
    
        int n, m;
        ll k;
        cin >> n >> m >> k;
    
        vector<int> a(n), b(m);
        for (int &x : a) cin >> x;
        for (int &x : b) cin >> x;
    
        // f[L] = number of row intervals of length L with all ones
        vector<ll> f(n + 1, 0), g(m + 1, 0);
    
        // compute f
        for (int i = 0; i < n; ) {
            if (a[i] == 0) { i++; continue; }
            int start = i;
            while (i < n && a[i] == 1) i++;
            int len = i - start;
            for (int L = 1; L <= len; L++)
                f[L] += len - L + 1;
        }
    
        // compute g
        for (int i = 0; i < m; ) {
            if (b[i] == 0) { i++; continue; }
            int start = i;
            while (i < m && b[i] == 1) i++;
            int len = i - start;
            for (int L = 1; L <= len; L++)
                g[L] += len - L + 1;
        }
    
        ll ans = 0;
        for (int L = 1; L <= n; L++) {
            if (k % L == 0) {
                ll W = k / L;
                if (W <= m) ans += f[L] * g[W];
            }
        }
        cout << ans << '\n';
        return 0;
    }