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

Gegenstand

Es gibt ein c aus den Arrays a und b, die nur aus 0 und 1 bestehen. (Elemente werden durch $ a [i] * b [j] $ erzeugt) ――Wie viele Quadrate mit der Fläche k existieren in diesem c?

Vertiefung des Verständnisses einer möglichen Matrix c

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)

Wenn du es versuchst

[[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]]

Wird erhalten, und es gibt einzeln "4 x 2, 4 x 3, 1 x 2, 1 x 3" Quadrate. Dies ist nichts anderes als eine Kombination von aufeinanderfolgenden 1-Zahlen in den Sequenzen a und b. Betrachtet man die Matrizen a und b, so ist a [4,1], b ist [2,3] und das obige Quadrat ist genau dieses Produkt.

Verstehe, wie man Quadrate mit der Fläche k zählt

Unter der Annahme, dass der Bruchteil von k x ist, betrachten wir ein Viereck von $ x \ mal k / x $. Hier ist ein Beispiel.

Wenn k = 4 ist, ist der Bruch [1,2,4], betrachten Sie also ein 1x4, 2x2, 4x1 Viereck.
Wenn k = 12 ist, beträgt die Anzahl der Reduktionen [1,2,3,4,6,12]. Betrachten Sie also die Quadrate 1x12, 2x6, 3x4, 4x3, 6x2, 12x1.
Wenn k = 13 ist, ist es eine Primzahl, also 1x13 und 13x1 Denken Sie nur darüber nach.

Wie viele Quadrate lx, ly können in einem Quadrat x, y existieren?

$ (x - lx + 1) * (y - lx + 1) $ Stücke. Es kann jedoch nicht existieren, wenn $ x-lx $ oder $ y-lx $ eine negative Zahl ist. Sie können dies sehen, indem Sie schreiben, wie viele 2x2, 1x3 und 1x2 im 3x3-Quadrat vorhanden sind.

Implementieren

Grundsätzlich kann das Obige implementiert werden. Mit anderen Worten --Zählen Sie fortlaufende Zahlen von 1 aus den Matrizen a, b und zählen Sie alle erstellten Quadrate (x, y) auf --Liste alle Kombinationen (lx, ly) auf, die ein Quadrat mit der Fläche k ergeben können --Zählen Sie, wie viele Quadrate (lx, ly) aller Bereiche k für alle Quadrate (x, y) der Matrix c existieren Wenn es jedoch ehrlich implementiert wird, wird es TLE sein. Da die Längen von a und b 40.000 betragen, wird bei einer Eingabe wie [0 1 0 1] ein Quadrat von 20000 x 20000 erstellt.

Daher werden die erstellten Dreiecke ohne Aufzählung mit (x, y, Zahl) gezählt. Wenn zum Beispiel a = [1,1,0,1,1], ist 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]]

Und es gibt vier 2x2 Quadrate, die das Produkt einer Liste aufeinanderfolgender 1 Zahlen sind. La = [2,2], lb = [2,2], Durch Speichern von la = (2: 2) und lb = (2: 2) kann ein 2x2-Dreieck als 2x2 berechnet werden. Dies wird es rechtzeitig schaffen.

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 = []
#Quadrat mit Fläche k(x,y)Aufzählen
for x in divs:
    rects.append((x, k // x))

from collections import Counter, defaultdict

#Array a,Generieren Sie ein Wörterbuch, das die Anzahl der aufeinanderfolgenden Längen von 1 aus b zählt
# [1,1,1,0,1,1,1,0,1,1] -> [3,3,2]Weil es die Länge von ist-> {3:2, 2:1}Werde ein Wörterbuch
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

#Anzahl
res = 0
for lx in da:
    for ly in db:
        for x, y in rects:
            #x aus a und b*Anzahl der y-Quadrate
            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:
                #Fügen Sie hinzu, wenn Sie machen können
                cannum = (cx + 1) * (cy + 1) * reccount
                res += cannum
print(res)

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