8월의 PS 일지 - Part 5

BOJ 19245 XOR

중요한 사실은 어쨌든 $T = xor(A) \oplus xor(B)$가 고정값이라는 것이다. 

만약 특정 비트가 $T$에서 꺼져있다면, 뭘 하더라도 $xor(A), xor(B)$는 그 비트에서 같은 값을 갖는다.

다른 말로 하면, 그 비트는 우리가 굳이 신경쓰지 않아도 된다는 것이다. 알아서 강제되기 때문이다.

이제 $T$의 가장 큰 비트를 $xor(A)$에게 준다고 하자. 이 시점에서 $xor(A) > xor(B)$는 강제된다.

이제부터 우리의 목표는 $T$에서 켜진 비트를 최대한 $B$에게 주는 것이다. 이를 확인하려면 뭐가 필요할까?

"특정 상위 비트에 대해서 이 비트마스크를 가질 수 있는가"를 판별하는 방법이 필요하다.

주어진 수들을 체 $\mathbb{F}_2$ 위의 벡터로 보고 기저를 만들자. 이제 가우스 소거로 이걸 할 수 있다. 

BOJ 19078 New Divide

결국 XOR prefix를 두 개로 쪼개서, 그 합을 최대화하는 것을 목표로 한다. 문제를 다르게 표현해보자.

어쨌든 쪼갠 두 값의 XOR 값을 고정이다. 또한, 첫 부분은 결국 이전에 등장한 XOR prefix가 된다.

즉, 값 $A$와 집합 $S$가 주어졌을 때, $x \in S$에 대하여 $x + (A \oplus x)$의 값을 최대화한다고 생각하자.

그런데 $x + y = x \oplus y + 2 (x \land y)$가 성립한다. 그러니 $x \land (A \oplus x)$를 최대화한다.

이건 결국, "$A$가 가지지 않는 비트 중 $x$가 갖는 비트"의 값을 최대화하는 문제가 된다.

마찬가지로 큰 비트부터 보면서, "이 mask를 포함하는 원소가 $S$에 존재하는가"를 물어보면 된다.

그런데 $S$는 쿼리를 대답하면서 커지는 집합이므로, 원소를 추가하면서 BFS를 조지면 이 쿼리를 쉽게 답할 수 있다. 

BOJ 19273 XorTree

모든 간선을 $0$으로 만드는 것은, 모든 정점의 "인접한 간선들의 가중치의 XOR"을 $0$으로 만드는 것과 동치다.

증명을 하려면, 단순히 리프부터 시작해서 올라가면 된다. 애초에 사이클이 없으니 자명하다.

이제 이 값을 정점의 값으로 부르도록 하자. 이제부터 간선에 대한 생각을 버린다.

또한, 특정 경로에 속한 간선들에 $x$를 XOR하는 것은, 경로의 양쪽 끝점의 값에 $x$를 XOR하는 것과 같다.

이제 훨씬 문제가 편해졌다. 이때 큰 가정을 하나 하자. 정점의 값이 같은 것이 2개가 있는 경우, 한 번의 시행으로 두 값을 $0$으로 만들 수 있다. 

이 시행을 무조건 하는 것이 이득이라고 가정해보자. 이제 문제를 풀 수 있다.

이 가정의 장점은, 현재 상태를 비트마스크로 쓸 수 있다는 것이다. "현재 홀수 개 존재하는 값의 집합"으로 보면 된다.

시작하자마자 같은 값을 갖는 정점 2개를 쌍으로 묶어 전부 0으로 만들고, 각 값이 최대 한 번 존재하도록 한다.

이제 "두 정점을 잡아 $x$를 XOR한 후, 두 개 이상 존재하는 값을 묶어 처리"하는 것을 상태 이전으로 볼 수 있다.

이러한 상태 이전은 그래프의 정점 (비트마스크) 사이의 간선으로 볼 수 있고, 이제 최단 거리 문제가 된다. 끝.

BOJ 19458 Expected LCP

$$E(f(s_1, s_2, \cdots, s_n)) = E( \sum_{k=1}^\infty [\exists_{1 \le i < j \le n} LCP(s_i, s_j) \ge k ])$$

$$ = \sum_{k=1}^\infty P(\exists_{1 \le i < j \le n} LCP(s_i, s_j) \ge k) = \sum_{k=1}^\infty \left( 1 - P(\forall_{1 \le i < j \le n} s_i[0,k) \neq s_j[0, k)) \right) $$

$$ = \sum_{k=1}^\infty \left( 1 - \frac{2^k(2^k-1) \cdots (2^k-n+1)}{(2^k)^n} \right) $$

가 되며 이는 전개 후 등비수열의 합으로 풀 수 있다. FFT를 쓰면 subquadratic 풀이도 가능. (분할정복/스털링 등)

BOJ 18956 Little Q and Big Integers

근본적으로 EGF를 생각하기 편한 구조가 되겠다. 우리가 원하는 EGF는 결국 $$ \prod_{i=1}^{k-1} \left( \sum_{j=0}^n \frac{g_{i, j}}{j!} x^j \right) $$가 된다. 여기서 $g$ 값들이 하나씩 바뀌는 것이 문제다. 모듈로가 NTT 모듈로고, 작으므로, 이 문제의 요령을 생각하자.

이제부터 적용할 모든 NTT는 다항식의 차수와 관계 없이 무조건 $2^{17}$으로 생각한다. 

그러면 NTT는 다항식 $f$가 주어지면 $f(w^0)$부터 $f(w^{2^{17}-1})$을 제공한다. 단, $w=t^6$이며 $t$는 원시근.

그러니 보통 우리의 요령은 각 $k-1$개의 다항식을 NTT하고, 그 결과를 pointwise 곱한 다음 역 NTT를 얹는 것이다.

그런데 이제 다항식이 바뀐다. 다행인 점은, 쿼리마다 다항식이 $k-1$개 중 하나만 바뀌고, 조금만 바뀐다는 것이다.

애초에 바뀌는 양이 단항식 하나라서, $f$ 값을 $\mathcal{O}(2^{17})$ 시간에 바꿔줄 수 있다.

또한, 바뀐 후의 pointwise 곱 역시 해당 위치 $k-1$개의 값 중 $0$의 개수 등을 관리하면 효율적으로 계산할 수 있다.

이렇게 하면 $g$ 값이 뒤집힌 이후에도 pointwise 곱 결과가 얼마인지를 빠르게 관리할 수 있다.

이제 이 결과를 전부 합친다음, 역 NTT를 하자. 여기서 NTT가 선형사상임을 이용하였다. 이러면 끝. 나쁘지 않다.  

BOJ 19570 삼각 분할

카탈란 문제니까 카탈란처럼 접근하자. $n$각형에서 빨간색 영역의 개수의 총합을 $f(n)$, 파란색 영역의 개수의 총합을 $g(n)$이라 하자.

$P_1P_2$가 속한 삼각형이 $P_1P_2P_k$라고 하자. 이 영역은 빨간색이 될 것이며, 양쪽은 $k-1$각형, $n-k+2$각형이 된다.

그러니 이때 추가되는 빨간색 영역의 개수는 $C_{k-3}C_{n-k} + C_{k-3} g(n-k+2) + C_{n-k} g(k-1)$이 된다.

이를 정리하면 $f(n) = \sum_{k=3}^n \left( C_{k-3}C_{n-k} + C_{k-3}g(n-k+2) + C_{n-k}g(k-1) \right) = C_{n-2} + 2 \sum_{k=0}^{n-1} C_k g(n-1-k)$가 된다. 

비슷하게 $g(n) = 2 \sum_{k=0}^{n-1} C_k f(n-1-k)$가 성립한다. 매우 생성함수가 필요해보이는 식이다.

그런데 그 전에 주의가 필요하다. 이 식만 보면 $f(2)=1$인데, 실제로는 $f(2)=0$이다. (index 문제) 나머지는 문제가 없다.

카탈란 수에 대한 생성함수를 $T(x)$, $f$에 대한 생성함수를 $F(x)$, $g$에 대한 생성함수를 $G(x)$라 하자.

여기서 우리는 $F(x) + x^2 = x^2 T(x) + 2 x T(x) G(x)$, $G(x) = 2xT(x)F(x)$가 성립한다. 

정리하면 $F(x) + x^2 = x^2T(x) + 4x^2T(x)^2 F(x)$가 성립하고, 결론적으로 $F$를 얻는다.

이를 실제로 계산하려면 $T(x)$를 어느 정도 계산하고, 다항식의 inverse를 계산하는 방법을 적용해야 한다.

이는 다항식 나눗셈 및 multipoint evaluation 등에 활용되는 부분이므로, 알아두는 것도 좋다.

다른 풀이로는 식의 형태를 보고 online FFT 각을 재서 푸는 방법이 있으며, 이 풀이가 정해였다고 한다. 18743번 참조. 

생성함수로 이렇게 풀리는 이상 polynomial coefficient의 recurrence가 존재할 것 같다. 실제로 존재한다. 얘 참고.

그래서 루트, 로그제곱 (online FFT), 로그 (생성함수 계산), 선형 (recurrence 유도) 풀이가 모두 있는 문제가 된다.

BOJ 19424 Power of Power Partition Function

이제부터 급수 $f(x)$의 $x^n$의 계수를 $f(x)[x^n]$이라고 표기하도록 하겠다.

이 문제도 생성함수로 접근한다. 그 근거는 convolution에 있는데, 이걸 진짜 convolution으로 생각하면 너무 힘들다.

그냥 생성함수를 생각한 후, 그 함수를 $k$승한 뒤 계수의 부분합을 구하라는 문제로 받아들이는 것이 편하다.

이제 $b_m(n)$의 생성함수를 생각하자. 이는 결국 $(1+x+x^2+ \cdots )(1+x^m+x^{2m}+\cdots) \cdots $와 같다.

그러니 이를 정리하면 $\displaystyle \prod_{t=0}^\infty \frac{1}{1-x^{m^t}}$를 얻는다. 이제 본격적인 풀이를 준비하자. 어쨌든 목표는 $\displaystyle \sum_{i=0}^n \left( \prod_{t=0}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i]$가 된다.

문제를 오히려 더 어렵게 만들어보자. 다항식 $P$가 있을 때, 이런 계산을 할 수 있다. $$ \sum_{i=0}^n P(i) \cdot \left( \prod_{t=0}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i] = \sum_{i=0}^n P(i) \cdot \sum_{j=0}^i \left( \frac{1}{(1-x)^{k-1}} \cdot \prod_{t=1}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^j] $$

$$ = \sum_{j=0}^n \left( \sum_{i=j}^n P(i) \right) \cdot \left( \frac{1}{(1-x)^{k-1}} \cdot \prod_{t=1}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^j] $$

$$ = \sum_{i=0}^n P^{*}(i) \cdot \left( \frac{1}{(1-x)^{k-1}} \cdot \prod_{t=1}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i] $$ 

여기서 $P^{*}$는 $P^{*}(i) = P(i) + P(i+1) + \cdots + P(n)$이 각 $0 \le i \le n$에 대해 성립하는 다항식이다. 

우리는 $P$를 $P^{*}$로 바꾸는 과정에서 $\displaystyle \frac{1}{1-x}$ 항을 하나 털었다. 이걸 $k$번 반복하면,

$$ \sum_{i=0}^n P^{*k}(i) \cdot \left( \prod_{t=1}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i] = \sum_{i=0}^{\lfloor n/m \rfloor} P^{*k}(m \cdot i) \cdot  \left( \prod_{t=0}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i] $$

이제 우리는 $P$를 $P^{*k}$로 바꾸면서 ($k$번 적용했다는 뜻이다) $n$을 $\lfloor n/m \rfloor$으로 털었다.

결국 이 과정을 $n=0$이 될 때까지 진행하면 된다. $P$를 $P^{*}$으로 바꾸는 과정을 효율적으로 하기만 하면 된다.

이는 Faulhaber's Formula 등을 통해서 할 수 있다. 적당히 뇌를 써서 효율적으로 하면 여유롭게 통과된다.