아주 오랫만에 새로운 글을 팠다...이번에는 조금 더 재미있는 수학을 하려고 수학적인 테마의 주제들을 가지고 왔다. 하지만 이 글이 써져있을 것을 기대하진 않을것이다... 왜냐하면 보통 내가 글을 처음 올린 시점에서는 대부분의 내용들이 비어있기 때문이다.
흠지금보니첫번째포스팅이랑이미지가겹치는군 바로 수정해야겠다. 뭐넣지
흠근데 수식이 뭔가 잘 안써지네 $1$
\( 1 \)
오 이렇게 하니까 되는군
1. LGV lemma
방금 배우고 왔는데, 굉장히 인상깊고 강력한 claim을 기반으로 하는 아이디어이다. 일단, 우리가 풀고자 하는 가장 주된 문제는 다음과 같다:
DAG가 주어지고, a_i에서 b_i로 가는 경로들의 쌍 \((P_1,...,P_n)\)의 개수를 세고 싶은데, 한 쌍 내에 존재하는 각 경로들은 동일한 정점을 가져서는 안된다.
물론 LGV lemma가 오직 이 문제만을 풀기 위해 존재하는 것은 아니고, LGV lemma를 통해 다룰 수 있는 다양한 문제들중 하나이다. 아마, 위에서 기술한 문제의 조건을 만족하는 가장 단순한 문제는 다음과 같을 것이다:
6556번: Paths on a Grid (acmicpc.net)
6556번: Paths on a Grid
The input contains several testcases. Each is specified by two unsigned 32-bit integers n and m, denoting the size of the rectangle. As you can observe, the number of lines of the corresponding grid is one more in each dimension. Input is terminated by n=m
www.acmicpc.net
뭐, 이 문제는 "물론" 굳이 LGV lemma를 쓸 필요도 없이, 조합론에 대한 조예가 충분하다면 그 풀이를 알 수 있는 단순한 문제이다. 다만 LGV lemma가 다룰 수 있는 문제의 종류를 설명하기 위해 가져왔다. 각 격자점들을 정점으로 하고, 격자선들에 방향을 부여한 DAG를 만들고 나면 이제 우리는 다음과 같은 경로의 쌍 (P_1)을 세어야 한다(단, P_1의 시작점은 왼쪽 아래이며 끝점은 오른쪽 위이다)(물론, 쌍이라는 이름이 무색하게도 사실상 하나의 경로이다.).
이 예제에 실망한 사람들을 위해, 조금은 더 복잡한 예시를 준비했다. 27533번: 따로 걸어가기 (acmicpc.net)
27533번: 따로 걸어가기
첫째 줄에 정수 $N$과 $M$이 공백을 사이에 두고 주어진다. ($2 \le N, M \le 200\,000$)
www.acmicpc.net
이 문제에 대해 잘 생각해보면, 이번에는 P_1이 (1,2)->(n-1,m), P_2가 (2,1)->(n,m-1)에 대응되는 쌍의 개수를 세면 된다는 사실을 알 수 있다. 반드시 그럴수밖에 없는 이유는, 만약 (1,2)->(n,m-1)인 P_1을 세려고 하면 필연적으로 (2,1)->(n-1,m)으로 가는 P_2와 공유하는 정점이 나타나기 때문에 우리가 구하고자 하는 전체 문제를 결국 다음과 같이 쓸 수 있다.
그렇다면, 이런건 어떻게 계산해야 할까?
이를 굉장히 간결하고 아름답게 계산할 수 있도록 해주는, 사실상 마법과도 같은 성질이 바로 LGV lemma이다!
LGV lemma의 진술은 약간 복잡한데, 이를 약간의 엄밀성을 포기하고 기술하면 다음과 같다:
DAG를 하나 생각하고, a_i에서 시작해서 b_i에서 끝나는 경로들 P_i를 생각하자. 그리고, DAG의 각 간선들에 가중치를 부여하자. 또한, W(P)는 경로 P 위에 있는 모든 간선들의 가중치의 곱이다. \(e(a,b)=\sum_{P:a\to b}^{}W(P)\)으로 정의된다. 즉, a에서 시작해서 b에서 끝나는 모든 경로들 P에 대해, 그 W(P)들의 총합이다. 여기에서 만약 모든 간선들의 가중치가 1이라면, e(a,b)는 a에서 b로 가는 경로의 개수임을 쉽게 확인할 수 있다.(그래서 보통 경로의 개수를 세려고 하면 그냥 간선들에 가중치를 1씩 부여하고 생각하기만 해도 보통은 충분하다.)
이제, 다음과 같은 n개의 경로들의 순서쌍을 \(P=(P_1,P_2,...,P_n)\)이라고 나타내자. 이때, 중요한 것은 꼭 P_1이 a_1에서 b_1으로 가는 경로일 필요는 없다는 점이다. 어떤 적당한 순열 \(\sigma\)가 존재해서, \(P_i:a_i\to b_{\sigma (i)} \)을 만족하는 모든 P들을 생각할 것이다. 또한, \(\sigma (P)\)는 그 경로의 순서쌍 P에 대해서 위에서 언급된, 조건을 만족하도록 하는 sigma로 잡을 것이다(이것이 하나라는 사실은 굉장히 자명하다. 왜냐하면 모든 경로는 저마다 시작과 끝이 있고, 모든 끝부분은 서로 다를 것이기 때문이다.).
이러한 조건 하에서, LGV lemma는 다음 명제를 제시한다. \(\begin{vmatrix}
e(a_1,b_1)) & e(a_1,b_2) & ... & e(a_1,b_n)\\
e(a_2,b_1)) & e(a_2,b_2) & ... & e(a_2,b_n)\\
... & ... & ... & ...\\
e(a_n,b_1) & e(a_n,b_2) & ... & e(a_n,b_n)
\end{vmatrix}=\sum_{P}^{}sign(\sigma(P))\prod_{i=1}^{n}w(P_i)\)
이 식이 무엇을 의미하는지 혼란스러울 수도 있다. 일단 우변은 굉장히 직관적으로 무슨 의미를 가지는지 해석할 수 있을 것이다. 단순히 각 시작점과 끝점의 쌍들에 대해 그 e값을 계산한 뒤, 이로 이루어진 행렬의 행렬식을 구하는 것이다.
우변은 어떠한가? 우리는 가능한 모든 n개의 경로의 쌍을 잡을 것이다(물론, 시작점과 끝점은 각각 a와 b들에 대응되며, 각 경로들은 공통된 정점을 가지지 않을 것이다.). 이 경로의 쌍에 대해서 위에서 정의한 sigma를 취하고, 그것의 sign을 취한다. 그 뒤 뒷부분에서는 내부의 모든 경로들에 대해 그 w값을 곱하는데, 사실 이 부분은 우리의 "간선들의 가중치를 전부 1로 설정한" 세팅에 따르면 1임을 알 수 있다.
이 식이 무엇을 의미하는가? 앞서 확인했던 문제를 생각해보자. 잘 생각해보면, 어차피 유일하게 의미가 있는 순열은 (1,2)를 (n-1,m)으로 보내고, (2,1)을 (n,m-1)로 보내는 순열이기 때문에, 우리는 답에서 (1,2)를 (n,m-1)로 보내고, 또 나머지도 적당하게 보내는 그 경로쌍들의 개수를 우리가 구하고자 하는 답에서 빼주어도 아무 상관이 없다(왜냐하면 그런 경로쌍은 존재하지 않기 때문에!). 따라서 우리는 그냥 왼쪽의 determinant를 계산하면 답을 구하게 된다.
증명을 찾는 사람들도 있겠지만, 솔직히 나는 증명을 이해할 자신이 없고, 먼 훗날 이해하게 되지 않을까 싶다. 이 lemma의 본질적 작동원리를 파악하는 것은 분명히 흥미로운 시도겠지만, 본 글에서는 LGV lemma의 결론이 얼마나 대단하고 범용적인지를 말하는 것이 주된 목표이기 때문이다.
결국, LGV lemma를 적용해보면 우리가 구하고자 하는 답은 놀랍게도, \(2(\binom{n+m-4}{m-2}^2-\binom{n+m-4}{m-1}\binom{n+m-4}{n-1})\)와 같은 굉장히 직관적인 식이 됨을 알 수 있다! (1,2), (2,1)에서 (n-1,m), (n,m-1)로 각각 가는 경로의 가짓수를 직접 계산하고 행렬식을 계산해보면 이해할 수 있을 것이다. 가장 앞에 2가 붙은 이유는 그냥 문제에서 두 마리의 토끼가 이동하는 경로가 바뀐 경우도 다르게 세었기 때문에 곱해준것 뿐이다.
코드는 당연하지만, 다음과 같이 굉장히 직관적으로 짤 수 있다.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod=1000000007;
ll n,m,i,s,a[1100000],t;
ll inv(ll x)
{
ll s=1,y=mod-2;
while(y)
{
if(y&1)
s=s*x%mod;
x=x*x%mod;
y>>=1;
}
return s;
}
ll comb(ll x,ll y)
{
if(x<y)
return 0;
return a[x]*inv(a[y])%mod*inv(a[x-y])%mod;
}
int main()
{
a[0]=1;
for(i=1;i<=400000;i++)
a[i]=a[i-1]*i%mod;
scanf("%lld %lld",&n,&m);
printf("%lld",((comb(n+m-4,m-2)*comb(n+m-4,m-2)%mod-comb(n+m-4,m-1)*comb(n+m-4,n-1)%mod+mod)%mod)*2%mod);
}
LGV lemma를 쓰면 조금 더 기상천외한 문제들도 해결할 수 있다! 예를 들면, 다음과 같은 문제를 생각할 수 있을 것이다:
n*m 격자판이 있고, 몇개의 칸으로는 이동할 수 없다. 항상 오른쪽, 위로만 갈 수 있다고 할 때, 가장 왼쪽 아래에서 오른쪽 위 꼭짓점으로 가는 경우의 수를 계산하여라.
보통 이런 문제는 조합에 대해 간단하게 배우는 학생들이 대충 두가지 정도의 풀이를 통해 해결법을 배우곤 한다.
1. 2차원 dp. 흔히들 쓰는 방법인데, 각 점들에 대해 자신의 왼쪽 점의 수와 아래쪽 점의 수를 합친다. 이렇게 하면 무조건 답이 계산된다.
2. 포함과 배제. 예를 들어 금지된 정점 하나를 무조건 지나는 경로의 개수를 세고, 두개를 무조건 지나는 경로의 개수를 세고, 이를 계속 반복하는 방식으로 계산할 수 있다. 분명 포함과 배제에 대해서는 좋은 예시가 될 수 있다고 본다.
그런데, 우리의 LGV는 무려 이 문제를 해결할 수 있게 해준다! 잘 생각해보면, 해당 문제는 다음과 같이 바꿀 수 있음을 알 수 있다:
a_1=(1,1), b_1=(n,m), a_i=b_i=(대충 i-1번째로 금지된 정점)일 때, 경로쌍을 세는 문제
왜 이러한 문제로 바뀔 수 있냐면, 첫번째 경로를 제외한 모든 경로들이 하나의 정점을 나타내게 되며, 그 정점들을 지나지 않는 첫 번째 경로들만이 counting될 것이기 때문이다! 이 문제는 역시 LGV를 통해 해결 가능하며, 사실 잘 생각해보면 조건을 만족하는 경로쌍의 순열은 반드시 항등원밖에 존재하지 않음을 쉽게 알 수 있다(왜냐하면 시작점과 끝점이 동일한 경로들에서, 끝점을 다른 경로들에게 할당하면 그 경로와 시작점이 공유되어 실패한다.). 따라서 이 문제를 해결할 수 있다. 물론 1번에 비해서 시간복잡도 면에서는 영 그닥이긴 하지만...
아니네 지금 생각해보니까 시간복잡도 측면에서도 특정한 상황이라면 1번을 압도한다. n*m이 굉장히 큰 경우엔 1번으론 못풀지만 만약 답을 특정한 법에 대해 구하는 상황이라면 뤼카 정리를 통해서 이항계수를 빨리 구할 수 있기 때문에 1번보다 더욱 빨리 푸는 경우가 존재할 것이다(즉, n과 m에 대한 시간복잡도가 크지 않다.)
10월 3일 기준, 백준에 lgv lemma 태그가 추가되었다는듯하다. 덕분에 몇가지 예제들을 찾을 수 있었는데, 그중 가장 기본문제스러운 것을 소개하겠다: 19514번: Intersection is Not Allowed! (acmicpc.net)
19514번: Intersection is Not Allowed!
Print $T$ lines, one for each test case. Each line must contain the number of different ways to move the pieces modulo $10^{9} + 7$.
www.acmicpc.net
2. Expected Value powers Technique
ㅁㄴㅇㄹ
3. SPFA
ㅁㄴㅇㄹ
4. 음이 아닌 다변수 선형 디오판토스 방정식의 해(congruence shortest-path problem)
대충 어떤 주제를 넣을지 생각하다가 굉장히 인상적인 모델링적 아이디어가 있어서 집어넣은 주제이다... 일단 기본적으로 디오판토스 방정식이 뭔진 알고, 선형 디오판토스 방정식이 무엇인지도 알 것이라 생각한다. 물론 몰라도 별 상관없다. 우리가 해결하고자 하는 문제는 다음과 같다:
\(\sum_{i=1}^{n}a_ix_i=K\)를 만족하는 음이 아닌 정수해 x는 무엇인가?(단, n<=500, 0<=a_i<=500)
사실, n, a_i들에 제한을 걸어두긴 했지만 구체적으로 시간복잡도는 O(n^2*min(a))가 된다. 즉, 상황에 따라서 제한이 다른 경우에도 충분히 적용될 수 있는 아이디어이다.
만약 n=1이라면, 단순히 K가 a_1의 배수인지만 판별하면 되는 굉장히 간단한 문제가 된다. n=2인 경우까지도 생각보다는 할만하다. 확장된 유클리드 알고리즘을 돌려서 특정한 해를 찾고 나면, 그 해들을 특정값만큼 더하고 빼는 것이 자유롭기 때문이다. 즉, 일종의 일차함수가 그려질 것인데 그중 제 1 사분면 위에 있는 정수해가 존재하는지만 판별하면 되서 쉽다. 게다가 굉장히 큰 a들에 대해서도 풀리기 때문에 사실 n=2인 문제를 풀고자 한다면 이 방법을 쓰는 것을 추천한다.
여기서 조금 여담이기는 한데, n=3인 경우까지도 상당히 흥미로운 분석이 이미 진행되어 있다. 일단 n=3인 경우의 해를 찾는 것은 n=2인 경우보다는 조금 어렵지만, 사실 어떻게든 할 수 있을 것 같다. 왜냐하면 어떤 숫자가 고정된 뒤에는 결국 n=2인 문제를 해결하는 것이 되는데, 그 첫 숫자가 어떤 선형적 조건을 만족해야 그 n=2인 문제에 해가 존재할 수 있는지는 적당한 수학적 계산을 통해 알아낼 수 있기 때문이다(귀찮아서 여기엔 적지 않았다.). 따라서 첫번째 숫자를 기반으로 이분탐색을 하는 방식이 꽤 유효할 것만 같은 느낌이 든다(그냥 직감적으로 말한 것이기 때문에 맹신해선 안된다). 그런데, 어떤 논문에서는 무려 n=3인 경우 해의 개수를 구하는 방법에 대해 기술해두었다! 나중에 이것도 언젠가의 포스팅에 올리게 될 것 같다. 심지어 그 시간복잡도도 대략 로그정도에 작동해서 굉장히 효율적이라고 한다.
아무튼, n이 500정도로 커지면 사실 답이 없어보이는 것은 사실이다. 이 경우엔 어떻게 해결할 수 있을까?
일단, 먼저 알고리즘을 제시하겠다. 편의를 위해 a들이 전부 정렬되어있다고 가정하자. 그리고, \(0~a_1-1\)까지의 숫자들을 정점으로 하는 그래프를 생각하자. 이때, 이 그래프는 방향그래프이며 2 이상의 x와 임의의 정점 t에 대해 \((t,(t+a_x)%a_1)\)로 가는, 가중치 a_x인 간선을 이어준다. 이제 0에서부터 시작해서 각 정점까지의 최단거리를 계산한다(이 부분이 시간복잡도를 지배한다). K를 a_1로 나눈 나머지를 k라고 하면, 정점 0에서 정점 k까지 가는 최단거리가 만약 K보다 작거나 같다면 해가 존재한다.
이런 알고리즘이 작동하는지 직관적으로 와닿기도 하고 아니기도 할 것이다. 일단 만약 이 방식으로 최단거리가 K보다 작거나 같다면 해가 존재함은 직관적으로 자명하다. 왜냐하면 같은 나머지를 가지면서, 더 작은 값이기 때문에 a_1을 적당히 더해주면 K를 construct할 수 있고, 사실 k의 경우에도 최단경로를 잘 역추적해주면 해의 구성 또한 역추적이 가능하다.
그렇다면, 만약 "해가 존재한다면 이 알고리즘으로 탐색"할 수 있을까? 사실, 이것이 불가능하다면 굉장히 쓰기 애매한 아이디어가 될 것이다.
결론적으로 말하면, 가능하다. 사실 이것도 꽤 직관적인데, 결국 우리가 만든 그래프 위에서 어떤 정점까지의 최단거리를 구했다는 것은 특정한 나머지를 가지는 값을 최대한 빠르게(즉, 작게) 만드는 방법을 계산한 것이기 때문이다. 그래서 아마도, 다음과 같은, 사실은 그냥 간단한 설명에 불과한 논증이 가능할 것이다.
만약 K를 만드는 방법이 존재했음에도 불구하고, 위 알고리즘에서 k로 가는 경로가 없거나 그 최단경로의 거리가 K보다 컸다고 하자. 그렇다면 K를 만드는 방법대로 따라가면 k로 가는 더 빠른 최단경로가 존재하므로 모순이다...
따라서, 이런 방법을 적용해주면 문제를 해결할 수 있다. 그래서 사실은 최대한 빠르게 0에서부터 각 정점까지의 최단거리를 계산하는 것이 핵심이 되는데, 여기에서 그냥 다익을 써서 적당히 풀 수도 있고, 혹은 SPFA를 써서 조금 더 빠르게 해결할 수도 있다. 나는 대충 SPFA를 쓰는게 좋다고 들었다.
뭐, 솔직히 이런 아이디어를 쓰는 문제가 별로 많을 것 같진 않지만...그래도 정수론에서 이런 그래프 모델링을 사용하는 것은 꽤 좋은 motivation이 될 수 있다. 뭐 예를 들면 다음과 같다:17133번: 라쿤이 정보섬에 올라온 이유 (acmicpc.net)
17133번: 라쿤이 정보섬에 올라온 이유
첫 번째 줄에는 네 개의 정수 N, M, K 그리고 R이 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 50, 2 ≤ K ≤ 500, 1 ≤ R < K) - N, M, K, R은 차례대로 라쿤 수, 솜사탕 종류, 솜사탕이 남는 나머지 수, 스티커를 사기
www.acmicpc.net
대충 이 문제도 문제에서 나온 조건을 간선으로 모델링해서 풀어야 했던 문제라고 생각한다. 뭐 지금 굳이 이 문제에 대한 설명을 할 필요는 없으리라 생각하고 그냥 여담으로 넘어간다.
흠...방금 솔브닥에서 그래프 이론과 정수론을 둘 다 쓰는 문제들을 대충 보고 왔는데 아무래도 이 아이디어를 쓰는 문제가 딱히 안보인다. 그래도 특수한 상황에서 이런 아이디어를 알고 있으면 역시 도움이 되지 않을까? 게다가 분명 icpc류의 문제들이 나오는 곳이라면 충분히 나올 가능성도 있고 말이다.
