RCC Final round C - Eleventh Birthday

Lobelia, RickMcCoy 와 함께 연습한 대회다. (팀명 : Red Lung)

나는 C를 잡았는데, 결과는 1 solve로 초라했지만 대회가 끝나고 1시간 가량 더 잡아서 풀어냈다.

(애초에 QR을 치려고 했는데 내가 예약을 FR로 잘못한 걸 나중에서야 알았다...)

$n$장의 서로 다른 카드에 숫자 $a_1, a_2, \cdots a_n$이 적혀 있다. ($1 \le a_i \le 10^{9}$) 이 카드들을 적당히 한 줄로 길게 이어붙여 만든 큰 숫자가 $11$의 배수가 되는 경우의 수를 $119 \times 2^{23} + 1$로 나눈 나머지를 구하여라. 

Tag : Combinatorics, Dynamic Programming, FFT, DP optimization with FFT

---

Step 0. Initialization

11의 배수판정법을 이용하면, $a_i$에서 중요한 것은 $11$로 나눈 나머지와 자릿수의 기우성 뿐임을 알 수 있다. 

전체 수의 나머지에 대해, 

어떤 수 $x$의 오른쪽 (낮은 자리)에 있는 수들의 개수가 홀수인 수는 $11-x$만큼,

오른쪽의 수 개수가 짝수인 수는 $x$만큼 기여할 것이다. (뭐라는거야...)

즉, 수를 이어붙이다가 자릿수가 홀수인 숫자가 나올 때마다, 나머지에 기여하는 "부호가 바뀐다".

따라서 $a_i$들을 2개의 vector에다가 자릿수의 기우성에 따라 분류하여 넣는데, $a_i \text{ mod } 11$을 벡터에 넣는다.

---

Step 1. 홀수 자릿수인 수들의 순열 개수 구하기

애초에 이 문제는 가능한 '순열'의 수를 구하는 문제이기 때문에 재귀적인 DP로는 잘 풀리지 않는다. 

즉, 가능한 '조합'의 수를 구한 뒤 거기에 팩토리얼을 곱하는 유형일 가능성이 높다.

홀수 자릿수인 수들을 11로 나눈 나머지를 각각 $o_1, o_2, \cdots o_b$라고 하자.

이들을 일렬로 순서대로 배열한 것을 오른쪽부터 $o_{\sigma_{1}}, o_{\sigma_{2}} \cdots o_{\sigma_{b}}$라 두면

$o_{\sigma_{2k}}$는 부호가 바뀌어서, $o_{\sigma_{2k-1}}$은 부호가 그대로 들어갈 것이다.

즉, $o_{i}$에 임의로 부호를 부여했을 때, 음수를 부여받은 숫자가 정확히 $\lfloor \frac{b}{2} \rfloor$개인 조합의 수에 $\lfloor \frac{b}{2} \rfloor ! \cdot \lceil \frac{b}{2} \rceil !$를 곱한 것이 홀수 자릿수 순열의 가능한 배열 개수가 된다.

조합의 수는 생성함수를 이용하여 구할 수 있는데, 먼저 $y^{11} = y^{0}$인 변수 $y$를 잡자.

여기서 $y$는 복소수가 아니고, 그래서 $y^{0} \neq 1$이다.일종의 벡터 $(a_{0}, a_{1}, \cdots a_{10})$를 다항식의 form $a_{0}y^{0} + a_{1}y^{1} + \cdots a_{10}y^{10}$로 생각하기 위해 도입한 변수이다.

$(a_{0}, \cdots, a_{10}) \times (b_{0}, \cdots, b_{10}) = (c_{0}, \cdots, c_{10})$이라고 하면

$c_{i} = \sum_{(i+j) \equiv k (\text{mod 11})} a_{i}b_{j}$이다. 이는 다항식의 곱과 매우 흡사한 form임을 알 수 있고, 

이것이 $y$의 직관적인 정의가 수학적으로 해괴하게 기술되는 이유이다.

각각의 $o_{i}$를 $(y^{o_{i}} + y^{(-o_{i})\text{ mod }11}x)$로 대응시킨 1차 다항식 $b$개를 모두 곱하는 것이다. 

이 과정은 FFT와 분할 정복을 이용하여 $O(b \lg ^{2} b)$에 수행될 수 있으며, $\text{mod}$가 좋으니 정수 FFT를 사용할 수 있다. 

(원시근은 $3$)

이 $b$차 다항식에서 $x^{\lfloor \frac{b}{2} \rfloor}y^{t}$의 계수가, 

$\lfloor \frac{b}{2} \rfloor$개의 숫자에 음수를 부여해서 적당히 합쳤더니 $\text{ mod 11}$로 $t$가 되는 조합의 수가 된다. 

이 벡터를 $A_{1}$이라고 하자.

---

Exception 1.1. $b = 0$인 경우

이 경우는 모든 수의 자릿수가 짝수이므로 답은 $0$ 또는 $n!$이다. $a_{i} \text{ mod } 11$을 다 더해서 0인지 체크해주면 된다. 

---

Exception 1.2. $b = n$인 경우

이 경우는 짝수 자릿수인 수가 존재하지 않으므로, $A_{1}$에서 $y^{0}$의 계수가 답이 된다.

아래는 $1 \le b \le n-1$인 경우를 생각한다.

---

Step 2. 짝수 자릿수인 수들의 순열 개수 구하기

이 경우는 조금 더 복잡하다. 

똑같은 풀이를 쓰는데 원하는 답은 다르다.

수학적인 상황으로는 홀수들을 '칸막이'로 생각하고,

음수를 부여받은 수들을 $2k$번째 칸막이와 $2k+1$번째 칸막이 사이에,

양수를 부여받은 수들을 $2k-1$번째 칸막이와 $2k$번째 칸막이 사이에 배치하도록 하는 경우의 수이다.

우선 $[x^{p}]$를 $x^p$의 계수 $a_{(p,0)}y^{0} + \cdots a_{(p,10)}y^{10}$이라고 생각하자.

짝수 자릿수 수들을 11로 나눈 나머지를 $e_{1}, e_{2}, \cdots e_{c}$라고 하자. ($b+c = n$)

이번에도 똑같이 $(y^{e_{i}} + y^{(-e_{i})\text{ mod }11}x)$를 다 곱한다.

동자순열(같은 것이 있는 순열)을 이용해서 머리를 잘 굴리면, 

$$\sum_{k=0}^{c} [x^k] \cdot \frac{(k+\lfloor \frac{b-1}{2} \rfloor)!}{\lfloor \frac{b-1}{2} \rfloor!}\cdot \frac{(c-k+\lfloor \frac{b}{2} \rfloor)!}{\lfloor \frac{b}{2} \rfloor!}$$

에서 $y^{k}$의 계수가 짝수를 잘 배치했을 때 $\text{mod 11}$로 $k$가 나오게 할 수 있는 순열의 수임을 알 수 있다.

따라서 위 식의 벡터를 $A_{2}$라고 하자.

---

Step 3. 답 구하기

$A_{1} \times A_{2}$의 $y^{0}$ 계수가 답이 된다. 저 곱하기는 당연히 외적이 아니라 위에 정의된 벡터곱이다. 풀이 끝!

Complexity : $O(11^{2} \cdot n lg^{2} n)$

---

FFT를 사용하지 않는 $O(11n^2)$ DP 풀이가 있는데, 나의 FFT 구현이 상당히 느림에도 불구하고 내 코드가 3배 이상 빠르다.