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배 이상 빠르다.