서론

https://github.com/ioi-2024/tasks/blob/main/practice/machine/statements/machine.pdf

이 문제를 풀어보자.

어디부터 시작해야 할까

일단 subtask의 condition을 볼때 use_machine을 호출하는 횟수가 대개 <=1 으로 되어있으니, use_machine을 딱 한번 호출해서 답을 구하는 게 가능하다는 것을 알 수 있다.

bitwise-XOR이니 각 bit에 대해 독립적으로 생각해볼 수 있다. 즉, xor mask X의 각 bit가 0일지 1일지를 각각 따로 계산하고, 그것들을 합쳐서 X를 구한 다음에, 그걸 가지고 permutation을 계산할 수 있겠다는 생각이 들었다.

각 bit에 대해 계산하는 방법

mask의 bit가 0이라면, 해당 bit는 변환 없이 use_machine의 반환값에 사용되었을 것이다. 즉 입력값의 bit가 0이면 0, 1이면 1이 되어야 한다. 반대로 bit가 1이면 반전될 뿐이다. 그럼… 입력값의 0의 갯수와 1의 갯수를 세고, 반환값의 0의 갯수와 1의 갯수를 세서 반전되었는지 아닌지 판단할 수 있으면 되지 않나?

이게 되려면 입력값의 0의 갯수와 1의 갯수가 달라야 한다.

즉 당면한 문제는 use_machine의 입력값 만들기

여윽시 테스트 문제라 문제 여기저기에 힌트가 많다. 이번에도 subtasks condition을 보면 M <= N + 2라는 조건이 있다. 즉, 0~N+2 사이의 숫자 중에서 N개를 고르는 방법 중에서, 모든 bit의 0의 갯수와 1의 갯수가 달라야 한다는 조건을 만족하는 경우가 존재할 거라는 소리다.

N+3개의 숫자 중에서 N개를 고르는 경우는 C(N+3, N) 가지의 경우의 수가 존재하기 때문에, N의 크기가 128로 충분히 작은 이런 문제에서는 손쉽게 N^3으로 다 돌려서 확인해볼 수 있겠다는 생각이 들었다.

N개를 고르는 게 아니라 N+3개 중에서 3개를 빼는 방식으로 하면 더 빠르다.

이게 최선인가

아마 수학적으로 접근하면 N^3보다 나은 방법이 있을텐데, 흐흐… 일단 답이 나오니까 최적화는 스킵이다.