โปรแกรมหาจำนวนสี่เหลี่ยมจัตุรัสในกริดใน Python

คำอธิบายโจทย์

ให้กริด p แถว q คอลัมน์ จุดวางเท่าๆ กัน หาจำนวนสี่เหลี่ยมจัตุรัส unique ที่มุมทั้ง 4 อยู่บนจุดกริด (ไม่จำเป็นขนานแกน) mod 10^9+7

ตัวอย่าง

p = 4, q = 4 → 20

วิธีแก้ปัญหา

สูตรทางคณิตศาสตร์: สำหรับแต่ละขนาด i (1 ถึง min(p,q)-1) จำนวนสี่เหลี่ยม = (p-i) × (q-i) × i
รวม: Σ (r-i)×(c-i)×i สำหรับ i = 0..min(r,c)-1

โค้ด Python

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))

อินพุต

p = 4 q = 4

เอาต์พุต

20