테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== A = B ⊕ C ======

===== 풀이 =====
  * 기본 아이디어는 [[https://github.com/ssu-sccc/2025scon/blob/main/editorial-slide.pdf|에디토리얼]] 에 설명되어있다
    * 원소 3개를 한 그룹으로 묶어서 생각할때, 1을 두개 0을 한개 사용하는 방법이 3가지, 0만 세개 사용하는 방법이 1가지
  * 그렇지만 에디토리얼에서는 이것을 기반으로 O(XY)의 DP로 푸는 방법만 설명하고 있는데, 실제로는 조합론적 풀이가 더 효율적이고 딱히 어렵지도 않다. 오히려 이게 더 쉬운 느낌인데..
    * 같은 에디토리얼에서 [[ps:problems:boj:33913]]번은 DP와 조합론적 풀이를 모두 설명했는데, 이 문제는 설명이 좀 부실하다.
  * 조합론적으로 풀면
    * 총 그룹의 개수는 (X+Y)/3 개이고, 그중에서 1을 두 개 사용하는 그룹은 X/2 개 이다. 그룹들을 배치하는 방법의 수는 C(X+Y/3, X/2)가지
    * 1을 두개 사용하는 그룹이 가질수 있는 형태는 3가지이다. X/2 개의 그룹이 각각 가질수 있는 형태를 생각하면 pow(3, X/2) 이다.
    * 결국 정답은 C(X+Y/3, X/2) * pow(3, X/2) 이고, 컴비네이션의 계산에는 O(X+Y), 거듭제곱의 계산에는 O(logX)가 걸리므로 총 시간복잡도는 O(X+Y)이다.
 

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 33914. A = B ⊕ C".

- Problem link: https://www.acmicpc.net/problem/33914
- Solution link: http://www.teferi.net/ps/problems/boj/33914

Tags: [combinatoric]
"""

import math

MOD = 10**9 + 7


def main():
    X, Y = [int(x) for x in input().split()]

    if X % 2 == 1:
        print('0')
        return

    n = (X + Y) // 3
    k = X // 2
    answer = math.comb(n, k) * pow(3, k, MOD) % MOD

    print(answer)


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}