https://codeforces.com/contest/1323/problem/B

Subject

--There is a c made up of arrays a and b consisting only of 0 and 1. (Elements are generated by $ a [i] * b [j] $) ――How many quadrangles with area k exist in this c?

Deepen understanding of the matrix c that can be done

a = [0,1,1,1,1,0,1]
b = [0,1,1,0,1,1,1]
c = []
for i in range(len(a)):
    l = []
    for j in range(len(b)):
        l.append(a[i] * b[j])
    c.append(l)
from pprint import pprint
pprint(c)

If you try

[[0, 0, 0, 0, 0, 0, 0],
 [0, 1, 1, 0, 1, 1, 1],
 [0, 1, 1, 0, 1, 1, 1],
 [0, 1, 1, 0, 1, 1, 1],
 [0, 1, 1, 0, 1, 1, 1],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 1, 1, 0, 1, 1, 1]]

Is obtained, and each of them has a rectangle of 4 x 2, 4 x 3, 1 x 2, 1 x 3. This is nothing but a combination of consecutive 1 numbers in arrays a and b. Looking at the matrices a and b, a is [4,1], b is [2,3], and the above quadrangle is exactly this product.

Understand how to count rectangles with area k

Assuming that the divisor of k is x, consider a rectangle of $ x \ times k / x $. Here is an example. --When k = 4, the divisor is [1,2,4], so consider a 1x4, 2x2, 4x1 quadrangle. --When k = 12, the divisor is [1,2,3,4,6,12], so consider the squares 1x12, 2x6, 3x4, 4x3, 6x2, 12x1. --If k = 13, it is a prime number, so 1x13 and 13x1 Just think about it.

How many quadrilaterals lx, ly can exist in a quadrangle x, y?

$ (x --lx + 1) * (y --lx + 1) $ pieces. However, it cannot exist when $ x-lx $ or $ y-lx $ is a negative number. You can see this by writing how many 2x2, 1x3 and 1x2 exist in a 3x3 rectangle.

Implement

Basically, the above may be implemented. In other words --Count the consecutive numbers of 1 from the matrix a, b and enumerate all the rectangles (x, y) created --List all combinations (lx, ly) that can create a quadrangle with an area k --Count how many quadrilaterals (lx, ly) of all area k exist for all quadrilaterals (x, y) of matrix c However, if it is implemented honestly, it will be TLE. Since the lengths of a and b are 40000, if there is an input such as [0 1 0 1], a quadrangle of 20000 x 20000 will be created.

Therefore, the triangles created are counted by (x, y, number) without enumerating. For example, if a = [1,1,0,1,1], b = [1,1,0,1,1]

[[1, 1, 0, 1, 1],
 [1, 1, 0, 1, 1],
 [0, 0, 0, 0, 0],
 [1, 1, 0, 1, 1],
 [1, 1, 0, 1, 1]]

And there are four 2x2 rectangles, which is the product of a list of consecutive 1 numbers la = [2,2], lb = [2,2]. By storing la = (2: 2) and lb = (2: 2), a 2x2 triangle can be calculated as 2x2. This will make it in time.

code

def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return divisors

n,m,k = map(int, input().split())
data = input().split()
datb = input().split()

divs = make_divisors(k)
rects = []
#Rectangle with area k(x,y)Enumerate
for x in divs:
    rects.append((x, k // x))

from collections import Counter, defaultdict

#Array a,Generate a dictionary that counts the number of consecutive 1 lengths from b
# [1,1,1,0,1,1,1,0,1,1] -> [3,3,2]Because it is the length of-> {3:2, 2:1}Becomes a dictionary
da = defaultdict(int)
db = defaultdict(int)
cnt = 0
l = len(data)
for i in range(l):
    if data[i] == "1":
        cnt += 1
    if data[i] == "0" or i == l - 1:
        da[cnt] += 1
        cnt = 0

cnt = 0
l = len(datb)
for i in range(l):
    if datb[i] == "1":
        cnt += 1
    if datb[i] == "0" or i == l - 1:
        db[cnt] += 1
        cnt = 0

#count
res = 0
for lx in da:
    for ly in db:
        for x, y in rects:
            #x made from a and b*Number of y rectangles
            reccount = da[lx] * db[ly]
            #print("{0} x {1} count = {4}, find {2} x {3} rect".format(lx, ly, x, y, reccount))
            cx = lx - x
            cy = ly - y
            if cx > -1 and cy > -1:
                #Add if you can make
                cannum = (cx + 1) * (cy + 1) * reccount
                res += cannum
print(res)

https://codeforces.com/contest/1323/submission/72671380