백준 15718 돌아온 떡파이어
23 Jun 2021https://www.acmicpc.net/problem/15718
m-1개의 날짜에 대해서 총 n이라는 떡국의 갯수를 나누어 주는 문제와도 같다. 이 때 각 날짜별로 떡국은 최소 1개는 있어야 한다. 이는 중복조합으로 달리 나타내면 n-1Cm-2와도 같다. 이 때 조합의 값을 100007로 나눈 값을 구하는 문제이다.
n과 m의 값이 크기때문에 이항계수를 구하는 문제는 dp로 접근할 수 없다. 따라서 앞에서 배운 뤼카의 정리를 써보려해도 100007은 소수가 아니기 때문에 어렵다. 놀랍게도 100007 = 97 x 1031 로 두 소수의 곱으로 이루어져 있다. 따라서 100007로 나눈 나머지는 97로 나눈 나머지와 1031로 나눈 나머지를 알아내면 중국인의 나머지 정리를 이용해 찾을 수 있게 된다.
중국인의 나머지 정리를 보면 알겠지만 a97n97s97 + a1031n1031s1031 (mod 100007) 로 최종 결과를 얻어낼 수 있다. 그런데 소수는 97과 1031로 고정되어 있기 때문에 여러 테스트 케이스에 대해서 n97s97과 n1031s1031을 계산할 필요가 없다. 따라서 미리 확장 유클리드 알고리즘을 이용해서 저장해둔 뒤 반복계산을 하지 않도록 해주자.
- 전체 코드
var combo:[[Int]] = []
func Euclid(a: Int, b: Int) -> Int {
var r1 = a, r2 = b, s1 = 1, t1 = 0, s2 = 0, t2 = 1
while r2 != 0 {
let q = r1/r2
let r = r1-q*r2, s = s1-q*s2, t = t1-q*t2
r1 = r2
s1 = s2
t1 = t2
r2 = r
s2 = s
t2 = t
}
return s1 > 0 ? s1 : b+s1
}
func lucas(n: Int, m: Int, p: Int) -> Int {
var N = n, M = m
var result = 1
while N != 0 && M != 0 {
result *= combo[Int(N%p)][Int(M%p)]
result %= p
N /= p
M /= p
}
return result
}
combo = Array(repeating: Array(repeating: 0, count: 1032), count: 1032)
combo[0][0] = 1
for i in 1...1031 {
combo[i][0] = 1
for j in 1...i {
combo[i][j] = (combo[i-1][j-1] + combo[i-1][j])%100007
}
}
let nsB = 97*Euclid(a: 97, b: 1031)
let nsA = 1031*Euclid(a: 1031, b: 97)
let t = Int(readLine()!)!
for _ in 0..<t {
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0], m = nm[1]
if n < m-1 {
print(0)
}
else if n == 0 {
if m == 1 {
print(1)
}
else {
print(0)
}
}
else if m == 1 {
print(0)
}
else {
let A = lucas(n: n-1, m: m-2, p: 97)
let B = lucas(n: n-1, m: m-2, p: 1031)
let result = (A*nsA + B*nsB)%100007
print(result)
}
}