Chương trình tìm số hình vuông trong lưới trong Python

Cho p hàng, q cột, các điểm phân bố đều. Tìm số hình vuông duy nhất (4 đỉnh tạo thành hình vuông, cạnh bằng nhau, không cần song song trục). Kết quả modulo 10^9+7.

Ví dụ: p = 4, q = 4 → 20.

Giải pháp

Công thức toán học: Tổng over i từ 0 đến min(r,c)-1 của (r-i)*(c-i)*i.

• i là "bán kính" hoặc tham số xác định hướng/cỡ hình vuông
• (r-i)*(c-i) là số vị trí đặt hình vuông
• Nhân với i cho các hướng khác nhau

Ví dụ minh họa

class Solution:
    def solve(self, r, c):
        ans = 0
        for i in range(min(r, c)):
            ans += (r - i) * (c - i) * i
        return ans % (10 ** 9 + 7)

ob = Solution()
print(ob.solve(4, 4))

Đầu vào

p = 4 q = 4

Đầu ra

20