BOJ 20791 Determinant Strikes Back

문제 링크입니다.

풀이

주어진 행렬의 형태가 단순해서, 이걸 더 단순화하면 쉽게 행렬식을 얻어낼 수 있을 것 같은 느낌입니다. 기본행연산 중 한 행에 다른 행의 상수 배를 곱해도 행렬식이 변하지 않음을 이용합시다.

x가 포함되지 않은 항들은 행끼리 모두 계수 $a$만 차이가 나니 이를 소거해주는 방향으로 연산을 합시다. 1행의 $a_i \over a_1$배를 $i$행에서 빼는 연산을 쭉 해주면 다음과 같은 행렬이 남습니다.

\[\begin{bmatrix} x+a_1b_1 & a_1b_2 & \cdots & a_1b_N \\ -{a_2 \over a_1}x & x & \cdots & 0 \\ \vdots & 0 & \ddots & 0 \\ - {a_N \over a_1} x & 0 & \cdots & x \end{bmatrix}\]

행렬식은 본질적으로 행렬에서 순열 뽑기입니다. 이때 0을 하나라도 포함하는 항은 무시해도 좋으니 우리는 딱 N개의 항만 확인하면 됩니다. 1행 1열을 선택하는 경우를 제외한 N-1가지 경우는 모두 1행 i열과 i행 1열, 나머지 행에서는 대각성분을 고르게 됩니다. 각 항을 더할 때 부호는 인버전 횟수의 기우성에 따라 결정되는데, 확인해보면 모든 항이 최종적으로 양수 부호를 가짐을 알 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const ll mod = 1e9+7;

ll n, x, a[1010101], b[1010101];

ll pw(ll n, ll r){
	ll ret = 1;
	while(r){
		if(r&1) ret = ret*n%mod;
		n = n*n%mod;
		r >>= 1;
	}
	return ret;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	while(cin >> n >> x){
		for(int i = 1; i <= n; i++) cin >> a[i];
		for(int i = 1; i <= n; i++) cin >> b[i];
		ll xx = pw(x, n-1);
		ll coef = (x+a[1]*b[1])%mod;
		for(int i = 2; i <= n; i++){
			coef = (coef+a[i]*b[i]%mod + 2*mod)%mod;
		}
		cout << coef*xx%mod << '\n';
	}
}