BOJ 15837:: Sum of Subrectangle Areas

https://www.acmicpc.net/problem/15837

쉬운 수학문제입니다.

$n^2$개의 각 1×1 정사각형마다 이를 포함하는 부분 직사각형이 몇 개인지 보면 됩니다. $i$행 $j$열 정사각형을 포함하는 부분 직사각형의 개수는 정사각형 위쪽에서 선 하나를 선택하는 가짓수 $i$, 왼쪽에서 선 하나를 선택하는 가짓수 $j$, 아래쪽에서 가짓수 $n-i+1$, 오른쪽에서 가짓수 $n-j+1$을 곱한 $ij(n-i+1)(n-j+1)$입니다. 이제 이걸 모든 $i$, $j$에 대해 더해주면 답이 되죠.

\[\sum_{i=1}^n\sum_{j=1}^n ij(n-i+1)(n-j+1) = \left[ \sum_{i=1}^n i(n-i+1) \right] ^2 = \left[ \frac{n(n+1)(n+2)}{6} \right] ^2\]

정답이 매우 크기 때문에 파이썬으로 구현했습니다.

t = int(input())
for i in range(t):
    n = int(input())
    print((n*(n+1)*(n+2)//6)**2)