12월 말 PS 정리 - Part 2

문제는 solved.ac 난이도 순이다. 전체적으로 난이도는 Platinum I ~ Ruby IV 정도로 높은 편이다.

BOJ 7737 삼각분할

\(T_n\)이 카탈란 수인 것은 유명하다. 이제 얘를 \(\pmod{m}\)으로 계산해야 한다.

\(m\)이 소수라면 팩토리얼 값을 전부 전처리한 다음에 계산하면 끝이지만, \(m\)이 합성수라서 문제가 꽤 매워진다.

\(C_{n+1} = \frac{2(2n+1)}{n+2} C_n\)이므로, 카탈란 수를 소인수분해된 형태로 저장할 수 있다.

그러니 각 소수를 leaf로 하는 곱셈 세그먼트 트리를 구성하면, 나눗셈 걱정 없이 문제를 해결할 수 있다.

\(\frac{2(2n+1)}{n+2}\)를 소인수분해한 다음, 이에 맞게 세그먼트 트리를 업데이트하면 된다.

BOJ 13127 도박과 사각형

Linearity of Expectation을 활용하는 문제다. 우선 \(E(S) = E(\sum_{v=1}^5 vc^2_v) = \sum_{v=1}^5 v E(c^2_v)\)다.

이제 \(E(c^2_v)\)를 구하는 방법을 생각해보자. \(S_{i,j}\)를 \([1,i] \times [1,j]\)에 존재하는 \(v\)의 개수라고 하자. 

\([i, k] \times [j, l]\) 사각형을 선택한다면, 이때 \(c^2_v\)의 값은 \((S_{k,l}-S_{i-1,l}-S_{k,j-1}+S_{i-1,j-1})^2\)이다. 

이를 전개하면 복잡한 식이 나오는데, 각각의 기댓값을 직접 계산할 수 있다. 꽤 고통스럽다.

\(S_{i,j}\)의 2차원 부분합을 계산하고, \(\sum_{i<j} 2x_i x_j = (\sum_{i} x_i)^2 - \sum_{i} x^2_i\) 등을 활용하면 된다.

BOJ 18151 DivModulo

\(D = p^{e_1}_1 p^{e_2}_2 \cdots p^{e_k}_k\)라 하자. 또한, \(\binom{m}{n} = p^{f_1}_1 p^{f_2}_2 \cdots p^{f_k}_k \cdot X\)라 하자.

우선 \(e_i\)들과 \(p_i\)들은 \(D\)를 소인수분해하여 쉽게 얻을 수 있다. 

그러니 \(f_i\)들도 \(v_p(n!) = \frac{n-s_p(n)}{n-1}\)이라는 공식을 이용하면 쉽게 얻을 수 있다.

여기서 \(D^t|\binom{m}{n}\)인 최대의 \(t\)도 얻을 수 있다. 이제 \(X \pmod{D}\)만 계산하면 답을 쉽게 얻을 수 있다.

\(X \pmod{p^{e_i}_i}\)를 각 \(i\)에 대해서 구한 다음, 중국인의 나머지 정리로 합치자.

\(m! = p^k \cdot Y\)라 할 때, (단, \(\text{gcd}(p,Y)=1\)) \(Y \pmod{p^e}\)를 \(f(m,p,e)\)라 하자. 

그러면 \(f(m,p,e) \equiv f(p^e-1, p, e)^{\lfloor \frac{m}{p^e} \rfloor} \cdot f(m \pmod{p^e}, p, e) \cdot f(\lfloor \frac{m}{p^e} \rfloor , p, e) \pmod{p^e}\)가 성립한다. 

각 \(0 \le i < p^e\)에 대하여 \(f(i,p,e)\)를 전처리하면, \(f(m,p,e)\)를 로그 시간에 계산할 수 있다.

한편, \(f(m,p,e)\)는 \(p\)와 서로소이므로, \(\pmod{p^e}\)에 대한 modular inverse를 생각할 수 있다.

이제 \(f(m,p,e)\)의 정의에서 \(\frac{f(m,p_i,e_i)}{f(n,p_i,e_i) \cdot f(m-n, p_i, e_i)} \equiv \prod_{j \neq i} p^{f_j}_j \cdot X \pmod{p^{e_i}_i}\)임을 알 수 있다.

이 식에서 modular inverse 등을 적당히 계산하면 \(X \pmod{p^{e_i}_i}\)를 계산할 수 있다.

BOJ 3435 Justice for All

아이디어는 전형적인데, 디테일을 생각하는 것은 조금 어려웠다. 재밌는 문제.

\(n\)개의 매칭이 있는 그래프를 \(2n\), \(2n+1\)개의 매칭이 있는 그래프로 바꿔보자.

\(n\)에서 \(2n\)으로 가는 것은 길이 4인 사이클을 추가해주면 간단하다. 

\(n\)에서 \(2n+1\)로 가는 것은 약간 애매하다. 정확히 하나의 매칭을 더 만들어야 한다. 

한 간선이 정해지면 다른 간선이 전부 강제로 정해져서 딱 하나의 매칭이 만들어지는 큰 그림을 그려보자.

작은 \(n\)에 대해서 적당히 실험을 해보면 방법을 찾을 수 있다. 

길이 4인 사이클을 추가할 때, 기존에 있던 그래프와 연결되도록 절선 간선을 적당히 하나 붙이자.

절선 간선이 추가되어도, 매칭의 개수는 변화하지 않음을 쉽게 알 수 있다.

이제 \(n\)에서 \(2n+1\)로 가보자. 먼저 앞선 방법처럼 길이 4인 사이클을 추가한 뒤 절선 간선을 적당히 하나 붙이자.

여기서 1번 정점에서 새로 추가한 정점으로 가는 간선을 하나 넣으면, 정확히 하나의 매칭이 추가됨을 알 수 있다.

BOJ 1665 화물열차

각 화물열차를 하나의 다항식으로 보면, 목표는 두 다항식을 곱했을 때 계수가 가장 큰 차수를 찾는 것이다.

\([a,b]\)에 컨테이너가 놓여있으면, 대응되는 다항식은 \(t^a+ \cdots + t^b = \frac{t^a-t^{b+1}}{1-t}\)다.

그러니 두 다항식의 곱은 \(\frac{1}{(1-t)^2} \cdot (\sum_{i=1}^n t^{X_i} - t^{Y_i+1}) \cdot (\sum_{i=1}^m t^{Z_i} - t^{W_i+1})\)이다.

편의상 \((\sum_{i=1}^n t^{X_i} - t^{Y_i+1}) \cdot (\sum_{i=1}^m t^{Z_i} - t^{W_i+1}) = \sum_i c_i t^{d_i}\)라 하자. 단, \(c_i \neq 0\)이다.

한편, \(\frac{1}{(1-t)^2} = \sum_{i=0}^\infty (i+1)t^i\)이므로, \(t^k\)의 계수는 \(\sum_{d_i \le k} c_i(k-d_i+1)\)이다.

이는 \(k\)에 대한 일차식이고, 그 일차식의 \(k\)에 대한 계수 \(\sum_{d_i \le k} c_i\)는 \(k=d_i\)에서 변화한다.

그러니 최댓값을 구하려면 \(k=d_i-1,d_i\)인 경우에만 \(t^k\)의 계수를 구하면 충분하다.

모든 계산은 lower_bound와 부분합 등을 적당히 활용하여 빠르게 할 수 있다. 메모리 제한에 주의하자.

BOJ 17643 Amusement Park

\(V(G) = [n] = \{1, 2, \cdots , n\}\)이라는 notation을 활용한다. 편의상 empty set은 independent set이 아니라고 하자.

주어진 그래프 \(G\)의 간선에 방향을 적당히 줘서, 사이클이 없도록 만들어주면 된다. 

DAG에서 각 간선의 방향을 전부 뒤집어도 DAG이므로, 답은 방향을 주는 방법의 수에 \(\frac{m}{2}\)를 곱한 값이다.

그런데 그래프의 acyclic orientation의 개수는 \(\chi_G(-1) \cdot (-1)^{|V(G)|}\)임이 알려져 있다. 

여기서 \(\chi_G(k)\)는 \(G\)의 chromatic polynomial이다. 

각 \(S_i\)가 \(G\)의 independent set이고, \(\sum_{i=1}^r |S_i| = n\), \(\cup_{i=1}^r S_i = [n]\)인 \(r\)-tuple \((S_1, S_2, \cdots , S_r)\)의 개수를 \(p(r)\)이라 하자. independent set으로 그래프를 분할한 것이다. 그러면 \(\chi_G(k) = \sum_{r=1}^n \binom{k}{r} p(r)\)가 성립한다.

그러니 여기에 \(k=-1\)을 대입하여 \(\chi_G(-1) = \sum_{r=1}^n (-1)^r p(r)\)임을 알 수 있다.

각 \(X \subseteq [n]\)에 대하여, 각 \(S_i\)가 \(G\)의 independent set이고 \(\sum_{i=1}^r |S_i| = n\)이며 각 \(i\)에 대해 \(S_i \cap X = \emptyset\)인 \(r\)-tuple \((S_1, S_2, \cdots , S_r)\)의 개수를 \(a_r(X)\)라고 정의하자. 포함-배제의 원리를 생각하면, \(p(r) = \sum_{X \subset [n]} (-1)^{|X|} a_r(X)\)가 성립한다. 정리하면 \(\chi_G(-1) = \sum_{X \subseteq [n]} \sum_{r=1}^n (-1)^{r+|X|} a_r(X)\)를 얻는다.

이제 \(X\)를 고정하고 생각하자. \(dp[i][j]\)를 [크기의 합이 \(j\)]인 [\(i\)개의 independent set]을 선택하는 방법의 수라고 하자. 

선택 순서는 중요하고, 각 independent set은 \([n] \setminus X\)에 속해야 한다. 크기가 \(k\)이고 \(X\)에 속하는 independent set의 개수를 \(S(X, k)\)라 하면 \(dp[i][j] = \sum_{k=1}^j dp[i-1][j-k] \cdot S([n] \setminus X, k)\)가 된다. 물론 \(a_r(X) = dp[r][n]\).

\(S(X, k)\)의 값들을 이미 계산했다고 생각하면, DP 테이블을 채우는데 \(\mathcal{O}(n^3)\)의 시간이 필요하다. 이를 각 \(X\)에 대해서 계산하려면 \(\mathcal{O}(n^3 2^n)\)의 시간이 필요해 TLE를 받는다. 하지만 우리가 계산해야 하는 값은 \(\sum_{r=1}^n (-1)^r a_r(X)\)이니, \(r\)의 홀짝성만 알면 된다. 그러니 DP 테이블의 정의를 변형할 수 있다. independent set의 개수 대신, 개수의 홀짝성만을 생각하면 된다. 이를 이용하면 DP 테이블을 \(\mathcal{O}(n^2)\)에 계산할 수 있고, 전체적으로 \(\mathcal{O}(n^2 2^n)\)의 시간에 계산을 마칠 수 있다. 

이제 남은 것은 \(S(X, k)\)의 값을 빠르게 계산하는 것이다. 먼저 각 \(2^n\)개의 부분집합이 independent set인지 여부를 미리 전처리하자. 이제 \(|X|=k\)이고 \(X\)가 independent set이면 \(F(X, k)=1\)이라고 두고, 그렇지 않으면 \(F(X, k)=0\)이라 하자. 여기까지는 \(\mathcal{O}(n2^n)\)에도 할 수 있다. 한편, \(S(X,k) = \sum_{Y \subseteq X} F(Y, k)\)가 된다. 이는 Sum over Subsets DP 테크닉을 이용하면 \(\mathcal{O}(n^22^n)\)에 계산할 수 있다. 이렇게 하면 모든 과정을 \(\mathcal{O}(n^2 2^n)\)에 할 수 있다. 끝.

굉장히 어려운 방법이지만, 이 풀이에서 배울 수 있는 점은 많다고 생각한다. 포함-배제 관련 테크닉은 다 할 수 있을 듯.

특히, 다른 사람들이 분할-정복 등의 복잡한 방법을 선택한 문제인 이 문제도 굉장히 쉽게 해결할 수 있다.

BOJ 10912 The Last Wizard

\( W = \{0, 1, \cdots , 9\}\)라고 하자. 마나 \(i\)의 양을 \(x_i\)라 하자. 

또한, \(i\)번째 경우에서 \(j\)번째 마나가 증가하는 양을 \(f_{i,j}\)라 하자.

\(T\)번의 수련 이후에 어떤 확률변수 \(X\)의 기댓값을 \(E(X, T)\)라 하자. 

각 \(S \subseteq W\)에 대하여 확률변수 \(\prod_{i \in S} x_i\)를 \(m_S\)라 하자.

특히, 특별히 (abuse of notation) \(E(S, T) = E(m_S, T)\)라고 정의하자. 

또한, \(A^T \cdot E(X, T) = P(X, T)\)라 하고, 마찬가지로 \(P(S, T) = P(m_S, T)\)라 하자. 

즉, \(P(X, T)\)는 가능한 모든 경우에 대한 \(X\)의 합이다. 이제 문제를 풀어보자.

\(\displaystyle E(S, T) = \frac{A - \sum_{i=1}^N P_i}{A} E(S, T-1) + \sum_{i=1}^N \frac{P_i}{A} \cdot E(\prod_{j \in S} (x_j+f_{i,j}), T-1) \)이 성립함을 알 수 있다.

이를 정리하면, \(\displaystyle E(S, T) = E(S, T-1) + \sum_{S' \subsetneq S} \text{coef}_{S', S} \cdot E(S', T-1) \) 형태의 식을 얻는다.

그런데 식을 자세히 보면, \(\displaystyle \text{coef}_{S', S} = \sum_{i=1}^N \frac{P_i}{A} \cdot \prod_{j \in S \setminus S'} f_{i,j}\)가 된다. 즉, \(\text{coef}_{S', S}\)는 사실 \(S \setminus S'\)에 의해서만 결정된다.

\(\displaystyle \text{coef}_{S', S} = \frac{1}{A} \cdot c_{S \setminus S'}\)으로 두면 \(\displaystyle E(S, T) = E(S, T-1) + \sum_{S' \subsetneq S} \frac{1}{A} \cdot c_{S \setminus S'} \cdot E(S', T-1)\)을 얻는다.

이제 \(A^T\)를 곱하면, \(\displaystyle P(S, T) = A \cdot P(S, T-1) + \sum_{S' \subsetneq S} c_{S \setminus S'} \cdot P(S', T-1)\)을 얻는다.

물론, \(c\)에 해당하는 값들을 계산하는 것은 \(\mathcal{O}(2^{10} \cdot N)\)에 할 수 있다.

이를 빠르게 계산하기 위해서, directed weighted graph \(G\)를 하나 구축하자. 

\(G\)의 정점은 \(W\)의 부분집합들이다. 각 점에는 weight \(A\)를 갖는 self-loop가 하나 있다.

또한, \(S' \subsetneq S\)이면 \(S'\)에서 \(S\)로 가는 가중치 \(c_{S \setminus S'}\)의 간선을 긋자.

또한, path \(P\)의 가중치를 \(P\)가 지나간 간선들의 가중치의 곱으로 (중복 포함) 정의하자.

이제 각 \(S \subseteq W\)에 대해서 \(P(S, 0)=1\)임을 생각하자. 그러면 \(P(S, T)\)는 [\(S\)에서 끝나고 \(T\)개의 간선으로 이루어진 모든 path]의 가중치를 더한 값임을 알 수 있다. 한편, 각 경로에서 self-loop가 아닌 간선은 최대 \(10\)개 뿐이다. 또한, 모든 self-loop의 가중치는 \(A\)로 동일하다. \(dp[S][i]\)를 [\(S\)에서 끝나고 \(i\)개의 [self-loop가 아닌 간선]만으로 이루어진 모든 path]의 가중치를 더한 값이라고 정의하자. 그러면 \(\displaystyle dp[S][i] = \sum_{S' \subsetneq S} dp[S'][i-1] \cdot c_{S \setminus S'}\)가 된다. DP 테이블을 채우는 것은 \(\mathcal{O}(10 \cdot 3^{10})\) 시간에 할 수 있다. 그러면 \(\displaystyle P(S, T) = \sum_{i=0}^{\text{min}(10, T)} dp[S][i] \cdot A^{T-i} \cdot \binom{T}{i} \)가 된다. \(A^{T-i}\)는 경로에서 \(T-i\)번 self-loop를 이용한 것에서 나오고, \(\binom{T}{i}\)는 \(T\)번의 간선 이동 중 언제 self-loop를 이용할 지를 결정하는 과정에서 나온다. 이항 계수는 \(i\)가 작으니 직접 계산하면 된다. 답은 \(P(W, T)\)다. 끝.

BOJ 17646 제곱수의 합 2 (More Huge)

먼저 필요한 제곱수의 개수를 판별하는 방법부터 알아보자. 

임의의 자연수는 4개의 제곱수의 합으로 표현할 수 있다. (라그랑주의 네 제곱수 정리)

\(4^a(8b+7)\) 형태의 자연수가 아니면, 3개의 제곱수의 합으로 표현할 수 있다. (르장드르의 세 제곱수 정리)

임의의 \(4k+3\)꼴 소수 \(p\)에 대하여 \(v_p(n)\)이 짝수면, 2개의 제곱수의 합으로 표현할 수 있다. (페르마의 두 제곱수 정리 활용)

마지막으로, 당연히 제곱수는 1개의 제곱수의 합으로 표현할 수 있다. 

그러니 필요한 제곱수의 개수는 pollard-rho 소인수분해를 이용하면 쉽게 판별할 수 있다. 여기까지가 이 문제.

이제 제곱수의 합으로 표현하는 방법을 생각해보자. 제곱수 1개가 필요한 경우에는 딱히 설명할 필요도 없다.

\(N\)을 표현하기 위해 제곱수 4개가 필요한 경우를 먼저 보자. \(N=4^a(8b+7)\)이라고 하자.

\(8b+6\)은 제곱수 3개로 표현할 수 있으므로, 그 방법을 찾아서 \(8b+6=x^2+y^2+z^2\)이라 하자.

그러면 \(N = (x \cdot 2^a)^2 + (y \cdot 2^a)^2 + (z \cdot 2^a)^2 + (2^a)^2\)이 된다. 끝.

\(N\)을 표현하기 위해 제곱수 3개가 필요한 경우를 보자.

\(x\) 이하의 자연수 중 두 제곱수의 합으로 표현될 수 있는 수의 개수는 대략 \(\displaystyle K \cdot \frac{x}{\sqrt{\ln x}}\)임이 알려져 있다.

여기서 \(K\)는 Landau-Ramanujan 상수다. 즉, 임의의 \(t\)를 하나 잡으면, \(N-t^2\)이 두 제곱수의 합으로 표현될 확률이 그렇게 나쁘지는 않다는 것이다. 그러니 \(t\)를 \(1\)부터 점점 증가시키면서, \(N-t^2\)을 두 제곱수의 합으로 표현하려고 시도하는 것을 반복하자. 성공하면 \(N-t^2=x^2+y^2\)을 얻고, 이는 결국 \(N=x^2+y^2+t^2\)이 된다. 끝. 

이제 \(N\)을 표현하기 위해 제곱수 2개가 필요한 경우를 보자.

\(N = T^2 \cdot p_1p_2 \cdots p_k\)라고 쓰자. 단, \(p_i\)들은 서로 다르며, \(2\)거나 \(4k+1\) 꼴 소수다.

페르마의 두 제곱수 정리에 의해, 각 \(p_i\)는 두 제곱수의 합으로 나타낼 수 있다.

라그랑주 항등식에 의해, [두 제곱수의 합으로 나타낼 수 있는 두 자연수의 곱]은 [두 제곱수의 합]으로 쉽게 나타낼 수 있다.

그러니 각 \(p_i\)를 두 제곱수의 합으로 나타내는 방법을 찾으면, 라그랑주 항등식을 반복해서 이용하면 끝난다.

여러 방법이 있지만 나는 이 글에서 소개된 (사진에 있다) Cornaccia's Algorithm을 사용했다. 

사진을 보면 알겠지만 Tonelli-Shanks Algorithm도 필요하다. overflow에 주의하자. int128을 적당히 사용하는 것을 추천.