cf #630 div2 E - Height all the same (수학, 집합)

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

 

<문제 설명>

n*m 그리드, 각 칸의 초기 높이 하한 상한 L,R이 주어진다.

 

인접한 두 칸의 높이를 1 늘리거나, 한 칸의 높이를 2 늘리는 작업을 마음대로 할 수 있을 때, 언젠간 모든 셀의 높이가 같도록 초기 그리드를 설정하고 싶다.

 

초기 그리드를 설정하는 경우의 수를 구하라.

 

<풀이>

높이를 맞추는 건 실제 높이가 중요하지 않고, 각 칸의 패리티가 중요하다. 모든 칸의 패리티가 같아질 수 있다면 그 초기 그리드는 유효한 그리드이다.

 

인접한 두 칸의 높이를 1씩 늘리는 것 -> 임의의 두 칸의 패리티를 바꾸는 것으로 생각할 수 있다.

(u->v로 하나씩 높이를 늘리는 연산을 하다보면, 결국 u,v의 패리티만 바뀌고 경로상의 칸의 패리티는 변하지 않는다.)

 

홀수패리티인 칸의 개수 a, 짝수 패리티인 칸의 개수 b라 하자.

 

n*m, 전체 칸의 개수가 홀수인 경우 a+b=홀수이므로 a또는 b는 짝수이다.

칸의 개수가 짝수인 패리티는 두 칸씩 골라서 칸의 개수가 홀수인 패리티로 바꿔줄 수 있다.

따라서 이 경우, 모든 상황에서 가능하다.

(R-L+1)^(n*m)

 

 

 

n*m이 짝수인 경우 모든 셀의 합이 짝수인 경우 그 격자판은 가능하다.

 

모든 초기 격자판(grid)을 생각해보자.
 -> 가능한 경우(셀의 모든 값의 합이 짝수인 경우 = 짝수인 셀의 개수가 짝수인 경우)
     불가능한 경우(그 외)로 나뉘어짐.

만약 가능한 격자판과 불가능한 격자판이 1대1로 짝을 이룰 수 있다면 답은 (total/2)가 될 것.
(모든 격자판의 수 = total)

 

(k = R-L)이 짝수인 경우와 홀수인 경우로 나눌 수 있다.

k가 홀수인 경우, total은 짝수이다.
모든 격자판의 아무 칸의 패리티를 바꿔준다. ( Aij ^= 1 )
패리티를 바꾸기 전의 모든 격자판의 집합을 X, 패리티를 바꾼 후의 모든 격자판의 집합을 Y라고 하면, X=Y이다.
이러면, 짝수인 셀의 개수는 홀수였으면 짝수가 되고 짝수였으면 홀수가 된다.
따라서 격자판의 패리티를 바꾸기 전에 불가능한 격자판이었으면, 가능한 격자판이 되고, 반대의 경우는 반대다.

가능한 격자판과 불가능한 격자판이 1대1로 짝을 이룰 수 있으므로 답은 (total/2)이다.


k가 짝수인 경우, total은 홀수이다.
모든 칸이 k인 격자판을 제외한 나머지 격자판의 k가 아닌 칸의 패리티를 바꿔준다.
모든 칸이 k인 격자판을 제외한 패리티를 바꾸기 전후의 집합은 위와 같이 같다.
격자판의 패리티를 바꾸기 전에 불가능한 격자판이었으면, 가능한 격자판이 되고, 반대의 경우는 반대다.

모든 칸이 k인 격자판은 가능하고,
모든 칸이 k인 격자판을 제외하곤 가능한 격자판과 불가능한 격자판이 1대1로 짝을 이룰 수 있으므로
답은 1 + (total-1)/2이다.

 

<코드>

ll n, m, L, R,e,o;

ll pow_(ll x, ll y) {
	if (y == 0) return 1;
	if (y == 1) return x;

	if (y % 2) return (x * pow_(x, y - 1)) % MOD;

	ll ret = pow_(x, y / 2);
	return (ret * ret) % MOD;
}

int main() {
	FAST; cin >> n >> m >> L >> R;
	if ((n * m) % 2) cout << (pow_(R - L + 1, n * m)) << '\n';
	else {
		ll ret = pow_(R - L + 1, n * m);
		if((R-L)%2)
			ret = (ret * (pow_(2, MOD - 2)) % MOD);
		else {
			ret = (((ret - 1+MOD)%MOD) * (pow_(2, MOD - 2)) % MOD);
			ret = (ret + 1) % MOD;
		}
		
		cout << ret << '\n';
	}
}

 

<생각>

모든 칸이 k인 경우 

k가 홀수인 경우 k값을 갖는 칸의 패리티를 바꾸면 그 칸의 값은 k보다 작은 값을 갖는다.

 

k가 짝수인 경우 k값을 갖는 칸의 패리티를 바꾸면 그 칸의 값은 k보다 큰 값을 갖게된다.

 

 

상황을 가능한 상황과 불가능한 상황으로 나누어 짝지어 경우의수를 헤아리는 방법은 일반적이라고 하니까 유념하자.

"There is a general solution to this kind of problems."