DP가 불가능할 때 특정 위치 (x,y)로 이동하는 경우의 수를 구하는 다른 방법

SW Expert Academy

SW Expert Academy

 

 

나이트가 (i,j)에 있을때, (i+1,j+2), (i+2,j+1) 둘 중 하나로만 움직일 수 있다고 하자.

 

x,y가 주어질 때, (0,0)에서 출발하여 (x,y)로 이동할 수 있는 경우의 수는?

 

dp[y][x] += dp[y-1][x-2], dp[y][x] += dp[y-2][x-1]로 구할 수 있을 것 같은데

 

X,Y가 $10^{6}$까지라서 메모리도 안되고 $O(N^{2})$이라 시간복잡도도 안된다

 

 

나이트가 (i,j)에서 이동하는 방법이 (i+1,j+2), (i+2,j+1) 2가지만 있다는 것을 생각한다면...

 

(0,0)에서 (i+1,j+2) = A를 a번 사용하고 (i+2,j+1) = B을 b번 사용하여 (x,y)로 이동했다고 하자.

 

즉, AAAAAA.....ABBBB....B를 순서대로 배열하는 모든 순열은 (0,0)에서 (X,Y)로 이동시킨다.

 

(0,0)에서 A를 a번하면 (a,2a)가 될 것이고 여기에 B를 b번하면 (a+2b,2a+b)가 된다.

 

A를 a/2번 하고 B를 b번하고 남은 A를 a/2번 해도 마찬가지로 (a+2b,2a+b)가 된다.

 

결국 A가 a개 있고 B가 b개 있는 순열의 수가 (X,Y)로 이동하는 경우의 수가 된다.

 

 

물론 실제로 (X,Y)로 이동이 불가능할 수도 있다.

 

x  = a+2by = 2a+b이므로... x,y가 주어지니까 a,b에 대한 연립방정식을 해결하면

 

a = (2y-x)/3b = (2x-y)/3이다.

 

a,b,x,y가 모두 정수이므로 2y-x, 2x-y가 3의 배수여야 한다.

 

또한 2y-x, 2x-y가 모두 0 이상의 음이 아닌 수여야 한다.

 

이러한 경우가 아닌 x,y이면 (0,0)에서 주어진 방법으로 이동할 수가 없다.

 

그러한 a,b를 찾았다면 A를 a개 B를 b개 배열하는 순열의 수는 복수순열이므로 $\frac{(a+b)!}{a!b!}$이다.

 

따라서 구하고자 하는 문제는 a,b가 존재한다면 x,y로부터 a,b를 구하고

 

$\frac{(a+b)!}{a!b!}$을 $10^{9}+7$로 나눈 나머지를 구하는 문제가 된다.

 

https://deepdata.tistory.com/1151

팩토리얼(factorial)의 소수 모듈로 곱셈의 역원(modulo inverse)을 구하는 기본적인 테크닉

 

 

$10^{9}+7$은 너무 유명한 소수이고 팩토리얼의 소수에 대한 곱셈의 역원을 구하는 방법은 위에서 정리해두었다

 

factorial = [0]*(10**6+1)
factorial_inverse = [0]*(10**6+1)

mod = 10**9+7

factorial[0] = 1

for i in range(1,10**6+1):
    
    factorial[i] = factorial[i-1] * i
    factorial[i] %= mod

factorial_inverse[10**6] = pow(factorial[10**6],mod-2,mod)

for i in range(10**6,0,-1):
    
    factorial_inverse[i-1] = factorial_inverse[i] * i
    factorial_inverse[i-1] %= mod
    
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    
    x,y = map(int,input().split())
    
    if 2*x-y >= 0 and 2*y-x >= 0 and (2*x-y) % 3 == 0 and (2*y-x) % 3 == 0:
        
        a = (2*y-x)//3
        b = (2*x-y)//3
        
        value = (factorial[a+b] * factorial_inverse[a] * factorial_inverse[b]) % mod
        
        print(f'#{t} {value}')
    
    else:
        
        print(f'#{t} {0}')