CR 630E: Height All the Same

Link

• http://codeforces.com/contest/1332/problem/E

• Codeforces Round #630 (Div. 2) E번

 

Tag

• 수학

Time Complexity

• $O(lg(NM))$

인접한 두칸을 골라 1씩 증가시키거나 한칸을 골라 2씩 증가시키는 연산을 할 수 있을 때, 모든 칸의 숫자를 같게 만들 수 있는, 각각의 수는 $L$ 이상 $R$ 이하이고 $N \times M$ 크기 격자의 갯수를 구해야 한다.

 

몇가지 관찰을 통해 해결할 수 있다.

 

먼저, 한칸을 골라 2씩 증가시키는 연산이 존재하기 때문에 각 칸의 홀짝성만이 중요하다.

 

두번째, 임의의 두 칸의 홀짝성을 바꿀 수 있다. 두 칸 사이의 경로에다가 인접한 두칸을 골라 1씩 증가시키면 경로상에서 두 칸의 홀짝성은 반전되고 나머지는 유지되기 때문이다.

 

세번째, $N \times M$ 이 홀수면 항상 가능하다. 이는 홀수나 짝수 둘 중 하나가 짝수개라는 뜻이므로, 두번째 관찰을 통해 전부 하나로 통일시켜주면 된다.

 

네번째, $N \times M$ 이 짝수면 ​ ​$\displaystyle \sum_{i=1}^N \displaystyle \sum_{j=1}^M a_{i,j}$ 이 짝수일 때만 가능하다. 이는 홀수인 칸의 개수가 짝수라는 뜻이므로, 세번째와 동일하다. 반대로 홀수인 칸의 개수가 홀수개일 때는, 어떠한 연산을 해도 전체 칸 끼리의 홀짝성이 유지되므로 하나로 통일시킬 수 없기 때문이다.

 

 

$H = R-L+1$, $E = [0, H]$ 의 짝수의 개수, $O = [0, H]$ 의 홀수의 개수로 정의하자.

먼저 $N \times M$이 홀수일 때는 그냥 $(H+1)^{NM}$이 답이 된다.

$N \times M$이 짝수일 때는 홀수칸의 개수가 짝수개여야 하므로 $\displaystyle \sum_{i=0}^{NM/2}E^{2i}O^{NM-2i} {{NM}\choose{2i}}$ 이다.

이항정리를 생각하면,

$(E+O)^{NM} = \displaystyle \sum_{i=0}^{NM/2}E^{2i}O^{NM-2i} {{NM}\choose{2i}} + \displaystyle \sum_{i=1}^{NM/2}E^{2i-1}O^{NM-2i+1} {{NM}\choose{2i-1}}$
$(E-O)^{NM} = \displaystyle \sum_{i=0}^{NM/2}E^{2i}O^{NM-2i} {{NM}\choose{2i}} - \displaystyle \sum_{i=1}^{NM/2}E^{2i-1}O^{NM-2i+1} {{NM}\choose{2i-1}}$

따라서

$(E+O)^{NM}+(E-O)^{NM} = 2 \displaystyle \sum_{i=0}^{NM/2}E^{2i}O^{NM-2i} {{NM}\choose{2i}}$이고, 최종적인 답은 $\frac{(E+O)^{NM}+(E-O)^{NM}}{2}$가 된다.

$E+O=H+1$ 이고, $E-O$ 는 $H$가 홀수일때 $0$, 짝수일때 $1$이다.

Code