BOJ 15902 - Split and Merge

문제

1x1, 1x2 조각으로 이루어진 1xL 격자에 대해, 초기 상태와 목표 상태가 각 상태를 이루는 조각의 수, 각 조각들의 너비로 주어진다.
e.g. 조각의 수가 4이면 1 2 2 1

1x1 두 개를 1x2로 만드는 연산과, 1x2를 1x1 두 개로 나누는 연산만 가능할 때, 초기 상태에서 목표 상태로 만드는데 필요한 최소 연산의 횟수와 그 횟수만큼의 연산을 수행해서 목표 상태로 만드는 경우의 수를 구하는 문제이다.

풀이

UCPC 2018 예선 풀이를 참고했다.

길이가 L인 격자가 주어지면 L-1개의 세로선이 존재할 수 있는데, 이 세로선들의 유무로 길이가 L-1인 bitstring을 만들 수 있다.
조각은 1x1, 1x2만 존재하기 때문에, bitstring에 연속된 0은 포함될 수 없다.

최소 연산으로 초기 상태 A에서 후기 상태 B로 만들어야 하기 때문에 두 bitstring에서 값이 같은 부분은 고려하지 않아도 된다.
두 bitstring을 비교해서 같은 부분을 제외하고 연산이 필요한 부분들로 쪼개면, 각 조각들은 0과 1이 번갈아가며 반복되는 형식이다.
(∵ 0이 연속할 수 없기 때문)
따라서 같은 위치에서의 A의 조각은 B의 조각에 NOT 연산을 수행한 결과이다.
e.g. 10111과 01101의 경우, [0, 1]과 [3, 4]로 쪼개진다.

이때, 임의의 bitstring T에 대해 NOT 연산을 수행해서 나온 bitstring T'는 T와 같은 경우의 수를 가진다.
(∵ T은 T'을 뒤집어 놓은 것과 같음)

길이가 N인 bitstring 0101...을 1010...으로 최소한의 연산을 사용해서 바꾸는 경우의 수를 \(D_n\)이라 하면, 아래와 같이 \(D_N\)의 점화식을 구할 수 있다.

\[\begin{align*} D_N &= {D_0 \times D_{N-1} \times {_{N-1}C_{0}}} + {D_2 \times D_{N-3} \times {_{N-1}C_2}} + ... \\ &= \displaystyle\sum_{i=0, 2, ...}^{N-1} {D_{i} \times D_{N-i-1} \times {_{N-1}C_i}} \end{align*}\]

• bitstring(0-indexed)에 대해, i는 연산을 수행할 0의 위치이다.
  i번째 자리의 0을 1로 바꾼 후에는 각각 길이가 i, N-i-1인 bitstring이 남는다.
  또한 1번의 연산을 수행했기 때문에, 남은 N-1번의 연산이 남았고, 두 bitstring의 연산은 서로 독립적이기 때문에, i번의 연산을 수행할 순서를 combination을 통해 정한다.

주어진 격자 1xL이 \(k\)개의 부분으로 나눠지고, \(i\)번째 부분의 길이가 \(L_i\)라고 하면, 문제의 답은 아래와 같다.

\[\frac {\displaystyle\prod_{i=1}^{k} {D_{L_i}} \cdot (\displaystyle\sum_{i=1}^{k} {L_i})!} {\displaystyle\prod_{i=1}^{k} L_{i}!}\]

• 가능한 모든 연산의 순서를 permutation으로 곱해주고, \(L_i\) 각각의 경우의 수는 \(D_{L_i}\)로 계산했기 때문에 \(L_i\)들의 가능한 연산의 순서는 다시 빼준다.

구현

문제에서는 답을 1000000007로 나눈 나머지를 출력해야 한다. L이 3000 이하라서 계산 중에 3000!처럼 long long의 범위를 훨씬 넘을 수 있기 때문에 모듈러 연산을 수행하는데, 답을 구하는 과정에서 나눗셈을 해야 한다.
덧셈, 뺄셈, 곱셈에 대해서는 계산할 때마다 모듈러를 구하면 되지만, 나눗셈은 모듈러 연산의 분배 법칙이 성립하지 않기 때문에 곱셈의 역원을 구해서 곱셈으로 바꿔서 계산해야 한다.

이때 페르마의 소정리를 사용해서 곱셈의 역원을 구해야 한다.

페르마의 소정리

• \(p\)가 소수이고, \(a\)가 \(p\)로 나누어지지 않는 정수이면
  \(a^{p-1} \equiv 1 \pmod{p}\)이다.
• 모든 \(a\)에 대하여
  \(a^p \equiv a \pmod{p}\)이다.

이 문제에서는 1000000007이 소수이고 \(p \nmid a\)이 보장되기 때문에 \(a\)의 곱셈의 역원은 \(a^{p-2}\)이다.

소스코드

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#define MOD 1000000007
using namespace std;
typedef long long lld;
typedef pair<int, int> pi;
typedef vector<int> vi;

lld power(lld n, lld m){
	lld res=1;
	while(m>0){
		if(m%2) res=(res*n)%MOD;
		n=(n*n)%MOD;
		m/=2;
	}
	return res;
}

int main()
{
	int L, n, m, cur;
	vi bstra, bstrb, bstrs;
	lld facto[3001], dp[3001], finv[3001];
	facto[0]=1, facto[1]=1, finv[0]=1, finv[1]=1, dp[0]=1, dp[1]=1;
	for(int i=2;i<3001;i++)	{
		facto[i]=facto[i-1]*i%MOD;
		finv[i]=finv[i-1]*power(i, MOD-2)%MOD;
	}
	
	scanf("%d %d", &L, &n);
	for(int i=0;i<n;i++){
		scanf("%d", &cur);
		if(cur==1) bstra.push_back(1);
		else {
			bstra.push_back(0);
			bstra.push_back(1);
		}
	}
	bstra.erase(bstra.end()-1);
	
	scanf("%d", &m);
	for(int i=0;i<m;i++){
		scanf("%d", &cur);
		if(cur==1) bstrb.push_back(1);
		else {
			bstrb.push_back(0);
			bstrb.push_back(1);
		}
	}
	bstrb.erase(bstrb.end()-1);
	
	cur=0;
	for(int i=0;i<L-1;i++){
		if(bstra[i]==bstrb[i]){
			if(cur==0) continue;
			bstrs.push_back(cur);
			cur=0;
		}
		else cur++;
	}
	if(cur) bstrs.push_back(cur);
	
	for(int i=2;i<=L;i++){
		for(int j=0;j<i;j+=2){
			lld t=1;
			t=t*dp[j]%MOD*dp[i-j-1]%MOD;
			t=t*facto[i-1]%MOD*finv[i-j-1]%MOD*finv[j]%MOD;
			dp[i]=(dp[i]+t)%MOD;
		}
	}
	
	lld cnt=0, A=1, B=0;
	for(int i=0;i<bstrs.size();i++){
		A=(A*dp[bstrs[i]])%MOD;
		cnt+=bstrs[i];
		A=(A*finv[bstrs[i]])%MOD;
	}
	B=facto[cnt];
	A=(A*B)%MOD;
	printf("%lld %lld", cnt, A);
	return 0;
}

풀고나서

• 팩토리얼은 곱셈의 역원도 많이 호출하기 때문에, 곱셈의 역원도 memoization 해놓으면 좋다.
• ncr mod p를 O(N)에 구하는 방법도 존재한다.