Online FFT 테크닉을 이용하여 해결할 수 있는 문제다. 여기서는 이 테크닉을 간단하게 설명한다.
배열 $a$가 주어져 있고, 이때 $c_i = \sum_{j=0}^i a_j a_{i-j}$를 구하고 싶다고 하면, 단순히 FFT를 적용하면 된다.
그런데 만약 $a_i$가 $c_i$와 관련된 값이라던가, 배열 $a$가 바로 주어지지 않고 online으로 주어지면 어떻게 될까?
이때는 단순한 FFT로는 해결하기가 어려우나, 분할 정복을 추가하여 해결할 수 있다.
여기서는 설명의 간단함을 위해 $a_0=0$이라고 가정하고, $c_i = \sum_{j=1}^i a_j a_{i-j}$를 계산해야 $a_i$를 얻을 수 있는 구조라고 생각하자.
카탈란 수의 점화식을 순수하게 FFT 하나로 계산한다고 생각하면 편할 것 같다.
$[L, R)$에 대해서, 문제를 해결하는 재귀함수 $f([L, R))$을 생각해보자. 이때 기본 가정은, 각 $L \le x < R$에 대하여 $a_0, a_1, \cdots, a_{L-1}$의 값을 이미 알고 있으며 각 $L \le t < R$에 대해 $p_L(x)^2 = \left( \sum_{i=0}^{L-1} a_i x^i \right)^2$의 $x^t$ 계수를 저장해놨다고 가정한다.
먼저 $M=(L+R)/2$를 잡고, $f([L, M))$을 호출하자. 이제 $f([M, R))$을 호출할 준비를 해보자.
현재 저장해놓은 $M \le t <R$에 대한 $p_L(x)^2$의 $x^t$의 계수들을 $p_M(x)^2$의 $x^t$의 계수들로 바꿔야 한다.
이는 결국 $(p_M(x)-p_L(x))(p_M(x)+p_L(x))$의 $x^t$ 계수를 구하는 것과 마찬가지다.
$p_M(x)-p_L(x)$는 $L$차 이상 $M$차 미만 단항식들로 구성되어 있다. 또한, 구해야 하는 계수는 최대 $R-1$차이다.
그러니, $p_M(x)+p_L(x)$의 $R-1-L$차 이하 단항식들만 고려해도 충분하다. 그러니 곱해야 하는 두 다항식의 실질적인 차수는 $R-L$에 비례한다. 개인적으로는 $L=0$인 경우를 따로 고려하는 것이 마음이 편하다. 어쨌든 정복 단계라고 볼 수 있는 스텝이 FFT로 $\mathcal{O}((R-L)\log(R-L))$에 된다.
그러니 총 시간복잡도는 $\mathcal{O}(N \log^2 N)$이 된다. 로그 하나는 순수한 분할정복에서 나오므로 꽤 빠르다.
이 문제와 매우 비슷한 형식을 가지고 있는 문제다. 마찬가지로 포함배제를 사용해보자. 편의상 $v_i = b^i - c + 1$이라고 쓴다.
그러면 식이 $\displaystyle \sum_{S \subset \{1,2, \cdots n\}} (-1)^{|S|} \binom{m+n-1-\sum_{i \in S} v_i}{m}$임을 쉽게 확인할 수 있다. 여기까지는 링크의 문제와 같다.
보통 이런 식이 나오면, $\sum_{i \in S} v_i$에 대한 다항식으로 이항계수를 생각하고 싶다.
그런데 여기서는 조합적 해석의 특성상, $a<b$에 대하여 $\binom{a}{b}$를 다항식의 값이 아니라 $0$으로 봐야 한다.
이걸 다루기가 꽤 까다로운데, 앞선 문제에서는 이를 meet in the middle 방식으로 해결했다.
여기서는 $v_i$의 특수한 형식 - 즉 지수적으로 증가하는 형태 - 를 극단적으로 활용할 수 있다.
$dp[i][j][k]$를 $\sum_{S \subset \{1,2, \cdots , i\}, |S|=j} \left( \sum_{t \in S} v_t \right)^k$라고 정의하자. 이는 식을 열심히 전개하여, $\mathcal{O}(m^4)$에 전처리를 할 수 있다.
이제 $\sum_{i \in S} v_i \le m+n-1$인 집합 $S$에 대해서만 다항식의 합을 계산해야 한다. 이는 Digit DP를 하듯이 계산할 수 있다.
큰 "비트"부터 내려가면서, 지금까지 뽑은 것을 봤을 때 나머지를 "자유롭게" 뽑을 수 있다면, 전처리한 DP 값을 활용하여 답을 구할 수 있다.
여기서 $v_i$의 지수적 증가를 활용한다. 전체적으로 문제는 $\mathcal{O}(m^4)$ 시간에 해결되며, 이는 PyPy3으로도 충분히 빠르게 돈다.
감동적으로 좋은 문제. 우선 많은 XOR 문제가 그렇듯이, 비트로 쪼갤 생각을 해야 한다.
$m_1 \ge m_2 \ge \cdots \ge m_n$이라고 하고, $2^t \le m_1 < 2^{t+1}$이 성립한다고 하자. 특히, $m_1$부터 $m_k$가 $2^t$ 이상이고, 나머지는 $2^t$ 미만이라고 하자.
우리는 기본적으로 $2^t$ 비트를 짝수개 뽑아야 한다. $1 \le i \le k$인 $i$에 대하여, $i$번째 변수에서 $2^t$를 뽑는다면 그 변수의 범위는 $2^t$에서 $m_i$가 된다.
그렇지 않는다면, $i$번째 변수는 $0$부터 $2^t-1$까지를 아무거나 뽑아줄 수 있다. 이는 굉장히 강력한 조건이며 이 문제의 핵심이다.
만약 $1 \le i \le k$ 중 $2^t$를 뽑지 않는 $i$가 있다면, 그 $i$를 제외하고 다른 변수들이 $2^t$ 비트만 제대로 맞춰주면 전체 XOR이 $0$이도록 $i$번째 변수의 값을 유일하게 결정할 수 있기 때문이다. 이를 생각하면, "처음으로 $2^t$를 뽑지 않는 index $i$"를 기준으로 카운팅을 해서 답을 얻을 수 있다.
만약 모든 $1 \le i \le k$에 대하여 $2^t$를 뽑는다면, $k$는 짝수여야 하며, $2^t$ 비트를 모두 제거했다고 가정하고 더 작은 문제를 해결하면 된다.
