33914번 - A = B ⊕ C
3개 단위로 쪼갰을 때 가능한 조합입니다.
1 => 1 01 => 0 10 => 1 10 => 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 정의에 의거하면 그 부분에서의 오류는 없는 것 같습니다.
대체 어디에서 문제가 생긴 것인지 알고 싶습니다.
반례입니다.
추가로, itertools.combinations 대신에 math.comb 함수를 사용하면 조합을 O(n) 정도의 시간에 구할 수 있습니다.
아, A가 Y보다 큰 경우를 잊었었네요. 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
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 정의에 의거하면 그 부분에서의 오류는 없는 것 같습니다.
대체 어디에서 문제가 생긴 것인지 알고 싶습니다.