BOJ 31469 아몬드 초콜릿

문제 링크입니다.

문제 요약

육각형 모양에서 꼭짓점을 포함하는 12개의 칸이 제거된 삼각 격자를 두 삼각형을 변끼리 붙인 모양으로 빈틈없이 채우는 방법의 수를 구하세요.

가로 위에 가로

격자를 이루는 가로선에 집중합시다. 가로선을 테두리에 포함하게끔 타일 하나를 놓으면, 그 위아래로는 마찬가지로 가로선을 테두리에 포함하게끔 타일을 놓아야 함을 알 수 있습니다. 이 연쇄는 타일이 전체 격자의 천장이나 바닥과 충돌하기 전까지는 멈출 수 없습니다.

가로선을 테두리에 포함하게끔 타일을 놓는 대신, 천장에서 바닥까지 가로선들을 one-by-one으로 잇는 경로를 만든다고 생각할 수 있습니다. 한 가로선에서는 바로 왼쪽 아래나 바로 오른쪽 아래로 내려가는 두 가지 방법 뿐이겠네요. 이때 사용되지 않은 가로선들은 해당 가로선을 중심으로 세로로 타일을 놓아 메울 수 있다는 의미가 됩니다. 또한 반드시 one-by-one으로 경로를 이어야 하므로, 윗변과 아랫변의 길이가 다르면 가능한 타일링이 없음을 알 수 있습니다. 이는 나머지 두 방향에 대해서도 동일합니다.

가로선은 동시에 그 바로 위의 정삼각형과도 같은 의미를 갖습니다. 타일을 겹쳐서 놓으면 안 된다는 제한이, 경로끼리 서로 겹치면 안 된다는 조건으로 환원됩니다. 겹치지 않는 경로 집합의 가짓수를 구하는 것은 Lindstrom-Gessel-Viennot 보조정리(LGV)로 구할 수 있습니다.

타일링 문제가 LGV 문제로 바뀌었습니다! 제한이 크지 않기 때문에 LGV에 필요한 각 경로의 가짓수를 하나하나 직접 구해줘도 괜찮습니다. 시간 복잡도는 ${\cal O}(\max(a,b,c)^4 )$정도 됩니다.

코드

#include<bits/stdc++.h>
#define x second
#define y first
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
const ll mod = 1e9+7;
ll mat[20][20]; int k;
bool valid[20][20]; ll d[20][20];
vector<pii> st, ed;

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

ll solve(pii s, pii e){
	if(s.y == e.y && s.x == e.x) return 1;
	if(s.y >= e.y || s.x > e.x) return 0;
	memset(d, 0, sizeof(d));
	d[s.y][s.x] = 1;
	for(int i = s.y; i < e.y; i++) for(int j = 0; j < 20; j++) if(valid[i][j]){
		d[i+1][j] += d[i][j];
		d[i+1][j+1] += d[i][j];
		d[i+1][j] %= mod;
		d[i][j+1] %= mod;
	}
	return d[e.y][e.x];
}

ll det(){
	ll ret = 1;
	for(int i = 1; i < k; i++){
		for(int ii = i; ii <= k; ii++){
			if(mat[ii][i]){
				for(int j = i; j <= k; j++) swap(mat[i][j], mat[ii][j]);
				break;
			}
		}
		if(!mat[i][i]) return 0;
		for(int ii = i+1; ii <= k; ii++){
			ll coef = mat[ii][i]%mod*inv(mat[i][i])%mod;
			for(int j = i; j <= k; j++){
				mat[ii][j] -= mat[i][j]*coef%mod;
				mat[ii][j] += 2*mod; mat[ii][j] %= mod;
			}
		}
	}
	for(int i = 1; i <= k; i++) ret = ret*mat[i][i]%mod;
	return ret;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f;
	if(a!=d || b!=e || c!=f) return !(cout << 0);
	for(int i = 1; i < a-1; i++){
		st.push_back({0,i});
		ed.push_back({b+c,i+b});
	}
	st.push_back({1,0}); st.push_back({1,a});
	ed.push_back({b+c-1,b-1}); ed.push_back({b+c-1,b+a-1});
	int L = 0, R = a;
	for(int h = 0; h <= b+c; h++){
		for(int i = L; i < R; i++) valid[h][i] = 1;
		if(h == b) valid[h][R-1] = 0;
		if(h == c) valid[h][L] = 0;
		if(h < b) R++;
		if(h >= c) L++; 
	}
	valid[0][0] = valid[0][a-1] = valid[b+c][b] = valid[b+c][b+a-1] = 0;
	k = st.size();
	for(int i = 1; i <= k; i++) for(int j = 1; j <= k; j++){
		mat[i][j] = solve(st[i-1], ed[j-1]);
	}
	cout << det();
}