백준 11402 이항 계수 4
23 Jun 2021https://www.acmicpc.net/problem/11402
nCk mod m을 구하는 문제로 뤼카의 정리를 실제로 활용해보는 문제이다.
알고리즘 설명하면서 다뤘던 내용을 한번 더 복습해보는 차원에서 풀어보았다.
변형할 것 없이 뤼카의 정리를 그대로 사용하면 되는 문제이다.
- 전체 코드
let nkm = readLine()!.split(separator: " ").map{CLongLong(String($0))!}
var n = nkm[0], k = nkm[1], m = nkm[2]
let IntM = Int(m)
var comb:[[Int]] = Array(repeating: Array(repeating: 0, count: 2001), count: 2001)
comb[0][0] = 1
for i in 1...IntM {
comb[i][0] = 1
for j in 1...i {
comb[i][j] = (comb[i-1][j-1] + comb[i-1][j])%IntM
}
}
var result = 1
while n != 0 && k != 0 {
result *= comb[Int(n%m)][Int(k%m)]
result %= IntM
n /= m
k /= m
}
print(result)