BOJ 24590 - Circle Bounce

오랜만에 풀어 보는 플래티넘 난이도의 문제다. 완전 깡수학 문제라서 마음에 들고, 풀이과정도 재미있는데다가 리저널 출신이라 많은 사람들이 풀어줬으면 좋겠다는 마음을 담아 지금부터 야무지게 추천하고 다니려고 한다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

당신은 완벽한 원형의 경기장 벽에 서서 테니스 공을 있는 힘껏 던졌다. \(n\)회 공이 벽에 튕긴 후, 그 다음 테니스 공이 벽에 부딪히는 곳은 어디일까?

경기장은 좌표평면의 원점을 중심으로 하는 반지름 \(1\)인 원이고, 당신은 \((-1,0)\)에 서 있다. 당신은 기울기가 \(a/b\)인 직선을 따라 테니스 공을 던진다. 벽과 테니스 공 간의 충돌은 완전 탄성 충돌이라 가정한다. 즉, 충돌로 인한 에너지의 손실은 전혀 없고, 입사각과 반사각은 같다. 아래 그림을 참조하라.

총 \(n\)회의 충돌 후, 공은 경기장 벽의 특정한 지점 \(p=(r/s,t/u)\)에 충돌하게 된다. 소수 \(M=1\,000\,000\,007\)에 대하여, \(r/s\pmod M\)을 출력하라.

입출력 조건을 만족하는 모든 경우에 대하여 \(p\)의 \(x\)좌표가 \(s\not\equiv 0\pmod{M}\)을 만족하는 기약분수 \(r/s\)이 됨을 증명할 수 있다. 이 때 당신은 \(ks\equiv r\pmod M\)을 만족하는 \(0\) 이상 \(M\) 미만의 정수 \(k\)를 출력해야 한다.

예를 들어, \(n=1\)이고 당신이 기울기 \(1/2\)인 직선을 따라서 공을 던지면 공은 먼저 \((3/5,4/5)\)에 충돌한다. 충돌 후, 공은 \((7/25,-24/25)\) 지점에서 경기장 벽과 만난다. \(25k\equiv 7\pmod{M}\)의 해는 \(k\equiv 960\,000\,007\pmod M\)이므로, 당신은 \(960\,000\,007\)을 출력하면 된다.

 

입력

첫 번째 줄에 세 정수 \(a,b,n\)이 공백으로 구분되어 주어진다. \((1\le a,b\le 10^9;\) \(1\le n\le 10^{12};\) \(\gcd(a,b)=1)\)

여기서 \(a/b\)는 당신이 처음 공을 기울기 \(a/b\)인 직선을 따라 던진다는 뜻이고 \(n\)은 충돌 횟수이다. \(a,b\)가 서로소임에 유의하라.

 

예제 입력)

# 예제 1
1 1 3

# 예제 2
1 2 1

# 예제 3
11 63 44

# 예제 4
163 713 980

 

출력

상술된 대로 하나의 정수를 출력하라. 예제 2는 문제 본문에 있는 예제와 동일하다.

 

예제 출력)

# 예제 1
1000000006

# 예제 2
960000007

# 예제 3
22

# 예제 4
0

 

---

내 코드

mod = 10**9+7
a,b,n = map(int,input().split())
init = [(a*a-b*b)%mod, (2*a*b)%mod, (a*a+b*b)%mod]
def add(p,q):
    p0,p1,p2 = p; q0,q1,q2 = q
    return [(p0*q0-p1*q1)%mod, (p0*q1+p1*q0)%mod, (p2*q2)%mod]
def mul(exp):
    if exp==0: return [1, 0, 1]
    if exp==1: return init
    X = mul(exp//2); X = add(X, X)
    if exp%2 == 1: X = add(init, X)
    return X
a,b,c = mul(n+1); print((pow(-c,-1,mod)*a)%mod)

 

모든 것을 \(y\)축에 대칭시켜 생각한다. 그러면 기울기가 \(-a/b\)인 직선을 따라서 \(A=(1,0)\)에 서서 공을 던지는 것과 같고, 마지막 답에 \(-1\)을 곱해 주(고 \(M\)으로 나눈 나머지를 취하)면 문제의 정답을 얻을 수 있다.

간단한 관찰 하나 : 최초 충돌한 지점이 \(P\)라고 하자. 동경 \(\vec{OP}\)가 각 \(\theta\)를 의미한다면, 문제의 답은 \(\cos(n+1)\theta\)이다. 이 관찰은 쉽게 할 수 있을 뿐더러 정당화도 간단하다. 매 충돌이 완전 탄성 충돌이고 그렇단 의미는 \(k\)번째 충돌 ~ \(k+1\)번째 충돌 사이의 공의 궤적은 항상 같은 길이의 선분이다. 현의 길이가 같으면 중심각도 같으므로 매 충돌 때마다 각이 \(+\theta\)가 된다고 생각해도 좋다. 각 \(\alpha\)인 동경과 원이 만나는 점의 \(x\)좌표는 \(\cos\alpha\)임이 잘 알려져 있으므로, 총 \(n+1\)회 충돌하였다면 점은 각 \((n+1)\theta\)인 동경 위에 있기 때문에 문제의 답이 \(\cos(n+1)\theta\)인 것까지는 쉽게 알 수 있다.

그래서 그 \(\cos(n+1)\theta\)가 무엇인지를 구하는 게 관건인데, 덧셈 법칙을 깡으로 이용한다거나 Chebyshev polynomial을 이용하는  이는 각을 다음과 같은 3-tuple과 동일시하는 식으로 풀 수 있다.

\[\theta=(a,b,c)\quad\left(\frac{a}{c}=\cos\theta,\frac{b}{c}=\sin\theta\right)\]

그러면 두 3-tuple의 덧셈을 \((a,b,c)+(a',b',c'):=(aa'-bb',a'b+ab',cc')\)으로 정의할 수 있고, \((n+1)(a,b,c)\)는 분할 정복을 통한 거듭제곱을 이용하여 구할 수 있다. \((n+1)\theta=(A,B,C)\)이면 최종 답은 처음에 \(y\)축 대칭을 시켜 준 것을 감안하여 생각하면 \(-A/C\)이다. 분모 역할이 되는 \(C\)는 \(c^{n+1}\)을 \(M\)으로 나눈 나머지이고, 이게 \(0\)이 될 수 없음은 자명하다. 분할 정복의 밑이 되어 줄 \((a_0,b_0,c_0)\)만 구해 주면 된다.

각 \(PAO\)를 \(\alpha\)로 두면, 반직선 \(AP\)의 기울기는 \(-a/b\)이고 따라서 \(-\frac ab=\tan(\pi-\alpha)=-\tan\alpha\)이다. \(\theta=\pi-2\alpha\)이고, 이를 이용해 덧셈 법칙을 사용하여 구해 주면 된다. 끝!

 

 

이로서 24590번의 풀이를 마친다.