BOJ 29150 - 기초적인 문제 (Python3)

BOJ 29150 - 기초적인 문제 (Python3)

2023. 9. 10. 20:41ㆍDiamond/Diamond V

SUAPC 2023 Summer B번 문제이며, 내가 출제한 세 번째 문제이다.

출제 여담은 SUAPC 2023 Summer 출제 후기에 충분히 썼으니 이번에는 이 문제의 수학적인 해결법에 대해 논하고자 한다. 에디토리얼에 있는 풀이 두 가지 대신 출제 때부터 마음 속에 품고 있었던 야매 풀이 하나와 어제 생각해 낸 제4의 풀이 이렇게 두 가지로.

그럼 본격적으로 풀이에 돌입해 보자.

문제

행렬식은 선형대수학에서 다루는 기초적인 대상 중 하나이다. 이항계수는 조합론에서 다루는 기초적인 대상 중 하나이다.

두 기초적인 대상을 섞은 문제는 기초적이므로, 다음 행렬의 행렬식을 구하는 문제는 기초적인 문제이다. $A (a_{1}, a_{2}, \dots, a_{N}) = {((\binom{a_{i}}{j - 1}))}_{i, j} = (\begin{matrix} (\binom{a_{1}}{0}) & (\binom{a_{1}}{1}) & \dots & (\binom{a_{1}}{N - 1}) \\ (\binom{a_{2}}{0}) & (\binom{a_{2}}{1}) & \dots & (\binom{a_{2}}{N - 1}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ (\binom{a_{N}}{0}) & (\binom{a_{N}}{1}) & \dots & (\binom{a_{N}}{N - 1}) \end{matrix})$

단, $(\binom{N}{K}) = {\begin{matrix} \frac{N!}{K! (N - K)!} & (N \geq K) \\ 0 & (N < K) \end{matrix}$ 는 이항계수이다.

기초적인 문제는 쉽게 풀 수 있으므로, 쿼리마다 정수 $a_{1}, a_{2}, \dots, a_{N}$ 이 주어지면 위 행렬의 행렬식을 구해보도록 하자.

입력

첫 번째 줄에 쿼리의 수 $Q$ 가 주어진다. $(1 \leq Q \leq 200)$

두 번째 줄부터 $2 Q$ 개의 줄에 걸쳐 쿼리에 대한 정보가 주어진다.

각 쿼리는 두 줄로 이루어져 있다. 쿼리의 첫 번째 줄에는 행렬의 크기 $N$ 이 주어지며, 두 번째 줄에는 $N$ 개의 음이 아닌 정수 $a_{1}, a_{2}, \dots, a_{N}$ 이 공백으로 구분되어 주어진다. $(1 \leq N \leq 500;$ $0 \leq a_{i} < 1 000 000 007)$

예제 입력)

1
3
4 5 7

출력

한 줄에 하나씩 순서대로 $det A (a_{1}, a_{2}, \dots, a_{N})$ 을 $1 000 000 007 (= 10^{9} + 7)$ 로 나눈 나머지를 출력한다. 정확하게는, $det A (a_{1}, a_{2}, \dots, a_{N}) \equiv M (\mod 1 000 000 007)$ 인 정수 $M$ 을 출력한다. $(0 \leq M < 1 000 000 007)$

예제 출력)

내 코드

mod = 10**9+7
fact = [1]*501
for i in range(2,501):
    """ fact[N] = N! """
    fact[i] = (fact[i-1]*i)%mod
hyper_fact = [1]
for i in range(1,501):
    hyper_fact.append((hyper_fact[-1]*fact[i])%mod)
def inv(x): return pow(x,mod-2,mod) 
def vandermonde(N,a):
    ans = 1
    for i in range(1,N):
        for j in range(i):
            ans = (ans*(a[i]-a[j]))%mod
    return ans
for _ in range(int(input())):
    N,a = int(input()),list(map(int,input().split()))
    print((vandermonde(N,a)*inv(hyper_fact[N-1]))%mod)

일단 거두절미하고 문제의 정답은 다음과 같다. $\prod_{i = 0}^{N - 1} \frac{1}{i!} \prod_{1 \leq i < j \leq N} (a_{j} - a_{i})$

우선 야매 풀이는 다음과 같다.

$n \times n$ 행렬 $X = (x_{i j})$ 의 행렬식은 $\sum_{σ \in S_{n}} (sgn (σ) \prod_{i = 1}^{n} x_{i σ (i)})$ 이 되고, 이는 변수를 $x_{i j}$ 로 가지는 $n$ 차 다항식으로 볼 수 있다.

주어진 행렬 $A (a_{1}, \dots, a_{N}$ 의 $i$ 번째 세로줄은 $(\binom{a_{j}}{i - 1})$ 의 꼴로, $i - 1$ 차 다항식임을 알 수 있다. 윗줄에 쓰여진 행렬식의 표현을 관찰한다면 $x_{i j}$ 는 동일한 $j$ 에 대해서 정확하게 한 번만 곱해진다는 사실을 알 수 있다. 그러므로 만일 $j$ 번째 열의 모든 원소가 정확하게 $j - 1$ 차 다항식이게 된다면, 행렬식은 $\sum_{j = 1}^{N} (j - 1) = \frac{N (N - 1)}{2}$ 차 다항식이 된다.

인수정리를 응용해 보자. 임의의 $i \neq j$ 에 대해서 $a_{i} = a_{j}$ 이게 되면, $i$ 번째 가로줄과 $j$ 번째 가로줄이 정확하게 같게 되므로, 행렬식의 성질(두 가로줄을 교환하면 행렬식의 부호가 바뀐다)에 의하여 $det A (a_{1}, \dots, a_{N}) = 0$ 이 된다. 그러므로 $det A (a_{i}, \dots, a_{N})$ 는 모든 $a_{j} - a_{j}$ 를 인수로 가진다.

$\prod_{1 \leq i < j \leq N} (a_{j} - a_{i})$ 는 $\frac{N (N - 1)}{2}$ 차 다항식이 되므로, $det A (a_{1}, \dots, a_{N}) = k \prod_{1 \leq i < j \leq N} (a_{j} - a_{i})$ 이 적당한 상수 $k$ 에 대해서 성립한다. 또한 $a_{i} = i - 1$ 를 대입하였을 시 $\prod_{1 \leq i < j \leq N} ((j - 1) - (i - 1)) = \prod_{j = 2}^{N} (\prod_{i = 1}^{j - 1} (j - 1)) = \prod_{j = 2}^{N} (j - 1)! = \prod_{i = 0}^{N - 1} i!$ 이 되며 $A (0, 1, \dots, N - 1)$ 은 대각성분이 각각 $(\binom{0}{0}), (\binom{1}{1}), \dots, (\binom{N - 1}{N - 1})$ 인 삼각행렬이 되므로, 행렬식이 $1$ 이 된다.

따라서 $k = \prod_{0}^{N - 1} \frac{1}{i!}$ 이 되고, 식을 정리하여 답을 얻을 수 있다.

네 번째 풀이는 그냥 행렬을 통째로 행연산을 반복하여 취함으로서 얻을 수 있다. 모든 열이 $a_{i}$ 만 다르고 동일한 형태를 가지고 있으므로, $(i, j)$ -component의 최저차항을 지우기 위해서 elementary row operation을 이용하면 임의의 $k$ 에 대해서 $(k, j)$ -component의 최저차항까지 전부 사라진다.

반복적인 elementary row operation을 통해서 각 열에 최고차항만 남길 수 있고, 그렇게 해서 얻어진 행렬은 다음과 같이 Vandermonde matrix와 굉장히 유사한 형태를 띄게 된다.

$(\begin{matrix} 1 & a_{1} & \dots & \frac{a_{1}^{N - 2}}{(N - 2)!} & \frac{a_{1}^{N - 1}}{(N - 1)!} \\ 1 & a_{2} & \dots & \frac{a_{2}^{N - 2}}{(N - 2)!} & \frac{a_{2}^{N - 1}}{(N - 1)!} \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 1 & a_{N - 1} & \dots & \frac{a_{N - 1}^{N - 2}}{(N - 2)!} & \frac{a_{N - 1}^{N - 1}}{(N - 1)!} \\ 1 & a_{N} & \dots & \frac{a_{N}^{N - 2}}{(N - 2)!} & \frac{a_{N}^{N - 1}}{(N - 1)!} \end{matrix})$

공통된 상수를 행렬식 앞으로 꺼내주고, Vandermonde determinant를 계산해 주면 결과를 얻을 수 있다.

이로서 29150번의 풀이를 마친다.

728x90

저작자표시 (새창열림)

'Diamond > Diamond V' 카테고리의 다른 글

BOJ 33414 - Bitvzhuh (0)	2025.07.24
BOJ 4149 - 큰 수 소인수분해 (Python3) (0)	2022.12.01

파이썬과 수학 블로그 nflight11 님의 블로그입니다.

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

파이썬과 수학 블로그

파이썬과 수학 블로그

태그

최근글

댓글

공지사항

아카이브

문제

입력

출력

내 코드

'Diamond > Diamond V' 카테고리의 다른 글

관련글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역