BOJ 32694 표식

나이브를 짜서 작은 입력에 대해 돌려보면 다음과 같은 결과를 얻을 수 있습니다.

W B even-odd
1 1 -1
1 2 1
1 3 -1
1 4 1
1 5 -1
2 1 -2
2 2 3
2 3 -4
2 4 5
2 5 -6
3 1 -3
3 2 6
3 3 -10
3 4 15
3 5 -21
4 1 -4
4 2 10
4 3 -20
4 4 35
4 5 -56
5 1 -5
5 2 15
5 3 -35
5 4 70
5 5 -126

이들의 절댓값은 이항 계수의 나열임을 짐작할 수 있고, 조금 더 생각해보면 ${W+B-1 \choose W-1}$임을 알 수 있습니다. 이제 이 값을 뤼카 정리를 써서 시간 내에 구할 수 있는 이항 계수들의 곱으로 바꾸고, 이러한 이항 계수들은 팩토리얼의 곱셈과 나눗셈으로 구해주면 됩니다.

증명은 생성함수를 사용하여 할 수 있습니다. $W$와 흰 정사각형의 개수 $i$를 고정하고, $b$를 수열의 인덱스로 하여 “흰 정사각형의 개수가 $i$이고 각각의 흰 정사각형 내의 도형의 수가 $W$이면서 총 검은 정사각형의 수는 $b$이고 모든 흰 정사각형 내에 검은 정사각형이 적어도 하나 있는 경우의 수"의 수열에 대한 생성함수를 나타내보면 다음과 같습니다.

• $i = 0$: $1$
• $i = 1$: $(1+x)^W - 1$ ($W$개 중 $b$개를 선택)
• $i = 2$: $(1+x)^{2W} - {2 \choose 1} (1+x)^W + {2 \choose 0} (1+x)^0$ ($2W$개 중 $b$개를 선택하는 방법에서 포함 배제 적용)
• $i = 3$: $(1+x)^{3W} - {3 \choose 2} (1+x)^{2W} + {3 \choose 1} (1+x)^W - {3 \choose 0} (1+x)^0$

여기까지 쓰고 $i$가 홀수인 경우의 합에서 짝수인 경우의 합을 빼면 다음을 얻습니다.

이제 이 합을 $i = B+1$까지 확장하면 $\frac{(1 - (1+x)^W)^{B+1} - 1}{(1+x)^W} = \frac{(1 - (1+x)^W)^{B+1}}{(1+x)^W} - \frac{1}{(1+x)^W}$가 됩니다. 여기서 첫 번째 항의 분자는 $x^{B+1}$의 배수이므로 $B$차 이하의 항의 계수는 0이고, $\frac{1}{(1+x)^W}$의 전개를 곱해도 그 사실은 달라지지 않습니다. 따라서 이제 $- \frac{1}{(1+x)^W}$의 $B$차 항을 구하기만 하면 됩니다.

분모에 $1+x$가 있는 경우, $-x$를 치환하여 정리한 다음 마지막에 $-x$를 대입하는 것이 유효합니다. 그러면 $\frac{1}{(1-x)^W}$는 어떤 수열일까요? 작은 $W$에 대해 확인해보면 다음과 같습니다.

• $W = 1$: $1, 1, 1, 1, 1, 1, \cdots$
• $W = 2$: $1, 2, 3, 4, 5, 6, \cdots$
• $W = 3$: $1, 3, 6, 10, 15, \cdots$

일반적으로, $\frac{1}{(1-x)^W}$는 $\sum_{i = 0}^{\infty} {W+i-1 \choose i} x^i$와 같습니다. 따라서 $-\frac{1}{(1+x)^W}$는 $\sum_{i = 0}^{\infty} (-1)^{i+1} {W+i-1 \choose i} x^i$이고, 우리가 구해야 하는 값인 $x^B$의 계수는 $(-1)^{B+1} {W+B-1 \choose B}$가 됩니다. 이 수는 $B$가 짝수면 음수이므로 짝수 팀이 이기고, $B$가 홀수면 홀수 팀이 이김을 알 수 있으며, 그 차이의 절댓값은 앞에서 규칙으로 유추한 결과와 동일합니다.