adfsfsf   1년 전

3개 단위로 쪼갰을 때 가능한 조합입니다.

1 => 1 0
1 => 0 1
0 => 1 1
0 => 0 0

즉, 1이 2개이고 0이 1개인 조합이 3종류, 0이 3개인 조합이 1종류입니다.

따라서 X는 항상 0 또는 짝수이고, (Y-(X/2))가 0 또는 3의 배수여야 조합이 존재합니다.

이제 X를 반으로 나눈 값을 A, (Y-A)를 3으로 나눈 값을 B라고 하겠습니다.
이들은 각각 (1이 2개, 0이 1개)인 덩어리의 개수, (0이 3개)인 덩어리의 개수입니다.
A 개의 덩어리는 각각 3가지 가능성 중 하나입니다.

따라서, 최종 출력은 다음과 같이 작성할 수 있습니다.

((3A)*(A+BCB))%1000000007

다만, python의 itertools에 있는 combinations를 쓰는 것은 너무 느리므로, 다음의 조합 계산식을 사용했습니다

A+BCB = (A+B)! / (A! * B!)

만약 반례가 있다면 제가 A나 B에 대한 조건을 잘못 이해했을 가능성만 떠올랐지만, 문제 가장 앞에 있는 XOR 정의에 의거하면 그 부분에서의 오류는 없는 것 같습니다.

대체 어디에서 문제가 생긴 것인지 알고 싶습니다.

kimhs   1년 전

반례입니다.

추가로, itertools.combinations 대신에 math.comb 함수를 사용하면 조합을 O(n) 정도의 시간에 구할 수 있습니다.

adfsfsf   1년 전

아, A가 Y보다 큰 경우를 잊었었네요. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.