두 개의 값 n과 m이 주어졌을 때, n × m 크기로 만들 수 있는 '겸손한 행렬(humble matrix)'의 총 개수를 구하는 것이 이번 문제의 목표입니다. 하나의 행렬이 겸손한 행렬이 되려면 다음 두 가지 조건을 모두 충족해야 합니다.
- 1부터 n × m까지의 모든 정수를 정확히 한 번씩 포함해야 합니다.
- 임의의 두 인덱스 쌍 (i1, j1)과 (i2, j2)에 대해 (i1 + j1) < (i2 + j2)라면, 반드시 Mat[i1, j1] < Mat[i2, j2]가 성립해야 합니다.
쉽게 말해 왼쪽 위에서 오른쪽 아래로 향하는 안티대각선(i + j 값)을 기준으로 볼 때, 앞쪽 대각선의 원소는 항상 뒤쪽 대각선의 원소보다 작아야 한다는 의미입니다. 만약 답이 너무 커진다면 결과를 10^9 + 7로 나눈 나머지를 반환하면 됩니다.
예시
예를 들어 입력이 n = 2, m = 2라고 가정해 보겠습니다. 이때 가능한 행렬은 다음 두 가지뿐이므로 출력은 2가 됩니다.
| 1 | 2 |
| 3 | 4 |
그리고
| 1 | 3 |
| 2 | 4 |
문제 해결 접근법
이 문제의 핵심은 팩토리얼 값을 미리 계산해 두는 것입니다. 조건상 같은 안티대각선 위의 원소들끼리는 서로 크기를 비교하지 않으므로, 각 대각선 내부에서는 원소를 자유롭게 배열할 수 있습니다. 따라서 답은 각 대각선 크기의 팩토리얼을 모두 곱한 값과 일치하며, 이를 n과 m의 크기 관계를 활용해 효율적으로 계산할 수 있습니다. 해결 절차는 다음과 같습니다.
- p := 10^9 + 7 (모듈러 값)
- result := 값 1로 초기화된 리스트 (팩토리얼 누적 저장)
- x를 2부터 10^6까지 반복하며 다음을 수행합니다.
- temp := result의 마지막 원소
- temp := (temp × x) mod p
- 계산된 temp를 result의 끝에 추가
- m > n이면 n과 m의 값을 서로 교환합니다.
- prod := 1로 초기화합니다.
- x를 1부터 m − 1까지 반복하며 prod := (prod × result[x−1]) mod p를 수행합니다.
- prod := prod² mod p로 제곱합니다.
- x를 0부터 n − m까지 반복하며 prod := (prod × result[m−1]) mod p를 수행합니다.
- 최종 prod를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
p = 10**9+7
def solve(n, m):
result = [1]
for x in range(2,10**6+1):
temp = result[-1]
temp = (temp*x) % p
result.append(temp)
if(m > n):
temp = n
n = m
m = temp
prod = 1
for x in range(1,m):
prod = (prod * result[x-1]) % p
prod = (prod**2) % p
for x in range(n-m+1):
prod = (prod*result[m-1]) % p
return prod
n = 3
m = 3
print(solve(n, m))입력
3, 3
출력
24
n = 3, m = 3인 경우 안티대각선의 크기가 차례로 1, 2, 3, 2, 1이므로 1! × 2! × 3! × 2! × 1! = 24가 출력됩니다. 이처럼 팩토리얼을 사전에 계산해 두면 큰 입력값에도 모듈러 연산만으로 빠르게 정답을 구할 수 있습니다.