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

Matière

--Il existe un c composé de tableaux a et b composés uniquement de 0 et 1. (Les éléments sont générés par $ a [i] * b [j] $) ――Combien de carrés d'aire k existent dans ce c?

Approfondir la compréhension de la matrice possible 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)

Si tu essayes

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

On obtient, et il existe individuellement des carrés «4 x 2, 4 x 3, 1 x 2, 1 x 3». Ce n'est rien d'autre qu'une combinaison de nombres 1 consécutifs dans les séquences a et b. En regardant les matrices a et b, a est [4,1], b est [2,3], et le carré ci-dessus est exactement ce produit.

Comprendre comment compter les carrés d'aire k

En supposant que la fraction de k est x, considérons un quadrangle de $ x \ fois k / x $. Voici un exemple. --Lorsque k = 4, la fraction est [1,2,4], alors considérons un quadrangle 1x4, 2x2, 4x1. --Lorsque k = 12, le nombre de réductions est [1,2,3,4,6,12], considérez donc les carrés 1x12, 2x6, 3x4, 4x3, 6x2, 12x1. --Si k = 13, c'est un nombre premier, donc 1x13 et 13x1 Pensez-y.

Combien de carrés lx, ly peuvent exister dans un carré x, y?

$ (x --lx + 1) * (y --lx + 1) $ pièces. Cependant, il ne peut pas exister lorsque $ x-lx $ ou $ y-lx $ est un nombre négatif. Vous pouvez voir cela en écrivant combien de 2x2, 1x3 et 1x2 existent dans le carré 3x3.

Mettre en place

Fondamentalement, ce qui précède peut être mis en œuvre. En d'autres termes

Compter les nombres consécutifs de 1 à partir des matrices a, b et énumérer tous les carrés (x, y) créés --Liste toutes les combinaisons (lx, ly) qui peuvent faire un carré d'aire k
Compter combien de carrés (lx, ly) de toutes les aires k existent pour tous les carrés (x, y) de la matrice c Cependant, s'il est mis en œuvre honnêtement, ce sera TLE. Comme les longueurs de a et b sont de 40 000, s'il existe une entrée telle que [0 1 0 1], un carré de 20000 x 20000 sera créé.

Par conséquent, les triangles créés sont comptés par (x, y, nombre) sans énumération. Par exemple, si 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]]

Et il y a quatre carrés 2x2, qui sont le produit d'une liste de 1 nombres consécutifs la = [2,2], lb = [2,2], En stockant la = (2: 2) et lb = (2: 2), un triangle 2x2 peut être calculé comme 2x2. Cela arrivera à temps.

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 = []
#Carré avec aire k(x,y)Énumérer
for x in divs:
    rects.append((x, k // x))

from collections import Counter, defaultdict

#Array a,Génère un dictionnaire qui compte le nombre de 1 longueurs consécutives à partir de b
# [1,1,1,0,1,1,1,0,1,1] -> [3,3,2]Parce que c'est la longueur de-> {3:2, 2:1}Devenir un dictionnaire
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

#compter
res = 0
for lx in da:
    for ly in db:
        for x, y in rects:
            #x fait de a et b*Nombre de carrés y
            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:
                #Ajoutez si vous pouvez faire
                cannum = (cx + 1) * (cy + 1) * reccount
                res += cannum
print(res)

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