https://doj.kr/ko/problems/30

아이디어

문제에서 구하는 정사각형이 '축에 평행하지 않을' 수 있다고 하였다. 즉, 아래와 같은 정사각형이 나올 수도 있음을 뜻한다.

그림의 정사각형은 한 변이 가로 2, 세로 1의 대각선이므로 이를 (2, 1)-정사각형이라 하자. 이제, 이에 외접하면서 축에 평행한 정사각형은 (3, 0)-정사각형임을 알 수 있다.

이를 일반화하면, ($i$, $j$)-정사각형의 외접 축평행 정사각형은 ($i+j$, 0)-정사각형임을 쉽게 생각할 수 있다. 이제 반대로 어떤 정사각형을 정했을 때, 자신을 포함해 이 정사각형에 내접하는 정사각형이 몇개인지를 생각해보자.

(3, 0)-정사각형에 내접하는 정사각형은 자신인 (3, 0)과, (2, 1), (1, 2)가 있음을 알 수 있다. 일반화해서 생각해봤을 때, ($p$, 0)-정사각형에 자신을 포함해 내접하는 정사각형은 $i+j=p$가 되는 모든 조합에서 가능하므로, $1 < i \leq p$에 대해 모든 ($i$, $p-i$)-정사각형임을 떠올릴 수 있다. 이로써 내접하는 정사각형은 $p$가 정해질 때 $p$개 있음을 보였다.

한편, $n \times m$ 직사각형 안에 $p \times p$ 정사각형이 들어갈 수 있는 개수는 다음과 같다.

이상을 정리하면 구하는 식은 다음과 같고,

$x=\min(n, m)$로 둔 뒤 자연수의 합 공식을 이용해 정리하면 다음과 같다.

모듈로 연산에 주의하고, 소수 $M:=1\ 000\ 000\ 007$에 대해 페르마 소정리를 적용해 역원

으로 모듈로 나눗셈을 구현하자.

코드 (Python)

M = 1_000_000_007
madd = lambda a, b: ((a%M) + (b%M)) % M
msub = lambda a, b: madd(a, M-b)
mmul = lambda a, b: ((a%M) * (b%M)) % M
mdiv = lambda a, b: mmul(a, pow(b, M-2, M))

n,m=map(int,input().split())

# n x m 직사각형에 p x p 정사각형이 들어갈 수 있는 개수는? (단 1 <= p <= min(n, m))
# : (n+1-p) * (m+1-p)
# p x p 정사각형을 AABB로 하는 정사각형의 개수는? -> p를 (i, p-i)로 분할하는 경우의 수 (i=1..p) = p

# 결론: sum[p = 1 to x := min(n, m)] (n+1-p) * (m+1-p) * p = sum p^3 - (n+m+2)p^2 + nmp
# = {x(x+1)/2}^2 - (n+m+2)(x(x+1)(2x+1)/6) + (n+1)(m+1)(x(x+1)/2)


x = min(n, m)
A = mmul(x, madd(x, 1))
B = mdiv(A, 2)

ans = madd(msub(mmul(B, B), mmul(madd(madd(n, m), 2), mdiv(mmul(A, madd(mmul(2, x), 1)), 6))), mmul(mmul(madd(n, 1), madd(m, 1)), B))
print(ans)

메모리 및 시간

• 메모리: 57.69 MB
• 시간: 23 ms

후기

• 백준 서비스 종료 후 첫 PS 포스트다. PS에 대해 대부분은 까먹었지만, 다행히 조금 까다로운 수학 문제라 풀 수 있었다.
• (수정 261013) 잘못된 표현(외접 정사각형의 세로는 0, 변수명 통일)을 수정했다.