두 개의 값 p와 q가 있다고 가정하고 점이 균일하게 배치된 p 행과 q 열이 있는 그리드에서 생성할 수 있는 고유한 정사각형의 수를 찾아야 합니다. 답이 매우 크면 결과는 mod 10^9 + 7을 반환합니다. 이 문제에서 정사각형은 정사각형의 4개의 꼭짓점을 형성하는 4개의 점의 집합입니다. 정사각형의 변의 길이는 동일해야 하며 항상 그리드의 축과 정렬될 필요는 없습니다.
따라서 입력이 p =4, q =4와 같으면 출력은 20이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
r에서 c의 최소 범위에 있는 i에 대해 수행,
-
ans :=ans +(r - i) *(c - i) * i
-
모드로 반환 (10^9 + 7)
-
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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