Codeforces Global Round 17 D. Not Quite Lee

Problem - D - Codeforces

D 치곤 너무 문제가 말도 안 되게 어렵고 이 문제를 풀어야 오렌지 퍼포먼스라니 글로벌 라운드라 그런가?

아무튼 여태 푼 D번중에 가장 어려운 문제였다.

정수론에 약한 면이 있어서 그럴 수도 있겠지만 개인적으로는 그렇다.

어떤 수열 c를 c1, c2, c3, ... 인 ci라고 하자.

수열 c가 good 인 상태를 판별하기 위해서 먼저 각 시퀀스 ci의 첫 시작을 0이라고 하자.

그렇게 되면 각 시퀀스의 총합은 ci(ci-1)/2 가 되고 각 시퀀스의 총합을 더한 전체 총합 s = ∑ci(ci-1)/2 가 된다.

여기서 s를 0으로 만들 수 있다면 good인 상태가 된다.

각 시퀀스의 총합은 시퀀스를 이루고 있는 개수만큼 총합이 움직일 수 있다.

따라서 s 를 0으로 만들기 위해서 s + x1c1+x2c2+…+xkck = 0를 만족하는 (x1, x2,…, xk) 해가 존재해야 한다.

x1c1+x2c2+…+xkck = -s 를 만족하는 (x1,x2,…,xk) 해가 존재해야 하므로

gcd(x1,x2,…,xk) = g 라 했을 때 s 가 g로 나누어 떨어져야 (x1,x2,…,xk) 해가 존재한다.

만약 g가 홀수라면 무조건 s가 g로 나누어 떨어진다.

왜냐하면 s = ∑ci(ci-1)/2 이고 ci는 g의 배수이다.

만약 ci가 홀수인 경우에는 s의 각 항은 ci로 나누어 떨어지므로 g로도 나누어 떨어진다.

ci가 짝수인 경우에는 ci가 g의 배수이고 g가 홀수이므로 ci = g*2*x (x는 임의 이 양의 정수)로 나타낼 수 있다.

g*2*x는 2로 나눠도 g가 남는다.

따라서 ci가 짝수인 경우에도 ci(ci-1)/2는 g로 나누어 떨어진다.

결론은 만약 g가 홀수라면 무조건 s가 g로 나누어 떨어진다.

g가 짝수인 경우만 확인을 하면 된다.

g가 짝수인 경우는 ci는 무조건 짝수다.

여기서부터는 g가 짝수인 경우를 확인하므로 ci가 짝수라고 가정하고 설명한다.

L를 g가 가지는 2의 인수의 개수라고 하자.

g는 2^L로 나누어 떨어지므로 이제 s가 2^L으로 나누어 떨어진다면 s가 g로도 나누어 떨어진다.

이제 s가 g로 나누어 떨어지는 경우를 확인할 필요가 없고 s가 2^L으로 나누어 떨어지는지만 확인하면 된다.

( s가 2^L으로 나누어 떨어지면 good인 경우이다. )

(1) 만약 ci가 2^(L+1)로 나누어 떨어질 경우, ci(ci-1)/2는 2^L로 나누어 떨어진다.

(2) 만약 ci가 2^(L+1)로 나누어 떨어지지 않을 경우, ci는 2^L로 나누어 떨어지므로 (g가 2^L로 나누어 떨어지고 ci는 g로 나누어 떨어지므로) ci(ci-1)/2는 2^(L-1)로 나누어 떨어진다.

여기서 결론은 ci(ci-1)/2는 무조건 2^L 또는 2^(L-1)로 나누어 떨어진다는 사실이고, 이를 응용하면

ci(ci-1)/2가 2^L으로 나누어 떨어지지 않을 때 나머지는 무조건 2^(L-1)이 생긴다는 사실이다.

결론은 2^(L-1) 이 짝수개가 존재하면 s가 2^L로 나누어 떨어지고

2^(L-1) 이 홀수개가 존재하면 s가 s^L로 나누어 떨어지지 않는다.

ci(ci-1)/2가 2^L으로 나누어 떨어지지 않을 때는 (2)인 경우이다.

따라서 ci가 2^(L+1)로 나누어 떨어지지 않는 ci가 짝수개일 경우면 good인 상태가 된다.

이를 해결하기 위해서는 먼저 L를 고정해 주어야 한다.

따라서 L이 가장 작은 경우부터 해결해야 한다.

cnt[L] 이 1보다 작을 경우에는 건너뛰어야 한다. ( cnt[i] : 2의 인수 i를 가지는 ci의 개수 )

왜냐하면 홀수개를 선택하는 것은 good인 상태가 아니기 때문이다.

x : cnt[L] + cnt[L+1] + cnt[L+2] + ... + cnt[L+3] 이라고 하자.

전체 부분집합의 수는 2^x이다.

여기서 cnt[L]에 포함되는 ci들 중에서 홀수개를 선택한 경우는 제외해 주어야 하므로 2^x / 2 = 2^(x-1) 이 된다.

그리고 cnt[L]를 선택하지 않고 cnt[L+1] ~ 에서만 선택된 부분집합의 경우의 수를 제외해 주어야 하므로

y : cnt[L+1] + cnt[L+2] + ... + cnt[L+3] 이라고 했을 때총 경우의 수는 2^(x-1) - 2^y 이 된다.

이제 L이 가장 작은 경우의 수를 해결했으므로

x = y

y = y - cnt[L+1]

되고 다시 똑같은 과정을 반복해 주면서 총경우의 수를 더해 주면 된다.

마지막으로 cnt[0]인 홀수인 경우를 더해 주어야 한다.

전체 경우의 수에서 짝수만 선택해서 만든 부분집합의 경우의 수를 빼주면 되기 때문에

2^n - 2^(n-cnt[0]) 를 마지막으로 더해주면 답이 된다.

 

정수론 너무 어렵다

이런게 왜 존재하는건가요?