lucas theorem, lucas, 뤼카 정리, nCr mod p, lucas-theorem
정의
뤼카 정리 (Lucas Theorem) 는 소수 p 에 대해 큰 n, r 의 이항 계수 nCr 을 p 로 나눈 나머지를 O(log_p N) 에 구하는 방법. n, r 을 p 진수로 전개한 각 자릿수에 대해 조합을 곱한 값이 nCr mod p 와 같다.
n = n_k p^k + ... + n_1 p + n_0r = r_k p^k + ... + r_1 p + r_0nCr ≡ ∏ n_i C r_i (mod p)
문제 상황과 동기
nCr mod p 를 구해야 하는데 n, r 이 10^18 까지 클 때.
naive (Pascal dp): O(n^2). n=10^6 도 불가.
팩토리얼 + 페르마 역원 (mod prime): O(n) 전처리. n < p 일 때만 작동. n >= p 면 분모에 p 의 배수가 들어가 역원 없음.
뤼카 정리: O(log_p N) 자릿수 순회. n 이 p 이상이어도 OK.
핵심 통찰: n 을 p 진수로 쪼개면, 각 자릿수 조합의 곱이 전체 조합의 mod p 값. p 소수일 때 (1+x)^n 의 전개에 p 진수 분해를 적용 (생성함수 증명).
시각화
핵심 아이디어
p 가 소수일 때 (1 + x)^p ≡ 1 + x^p (mod p) 가 성립 (Frobenius endomorphism).
n = n_0 + n_1 p + n_2 p^2 + ... + n_k p^k(1+x)^n = (1+x)^(n_0) · ((1+x)^p)^(n_1) · ((1+x)^(p^2))^(n_2) · ... ≡ (1+x)^(n_0) · (1+x^p)^(n_1) · (1+x^(p^2))^(n_2) · ... (mod p)x^r 의 계수 = 각 자릿수에서 n_i C r_i 의 곱
알고리즘
nCr_mod_p(n, r, p): if r > n: return 0 res = 1 while n > 0 or r > 0: ni = n % p ri = r % p if ri > ni: return 0 # 자릿수 조합 = 0 res = res * C_small(ni, ri) % p n /= p r /= p return resC_small(n, r): # n, r < p return fact[n] * inv_fact[r] * inv_fact[n-r] % p
구현
// Lucas Theorem, O(log_p N)#include <bits/stdc++.h>using namespace std;using ll = long long;ll modpow(ll a, ll b, ll m) { ll res = 1; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res;}ll nCr_small(ll n, ll r, ll p) { if (r > n) return 0; ll num = 1, den = 1; for (ll i = 1; i <= r; i++) { num = num * (n - i + 1) % p; den = den * i % p; } return num * modpow(den, p - 2, p) % p;}ll lucas(ll n, ll r, ll p) { ll res = 1; while (n > 0 || r > 0) { ll ni = n % p, ri = r % p; if (ri > ni) return 0; res = res * nCr_small(ni, ri, p) % p; n /= p; r /= p; } return res;}int main() { ll n, r, p; cin >> n >> r >> p; cout << lucas(n, r, p) << "\n";}
# Lucas Theorem, O(log_p N)def ncr_small(n, r, p): if r > n: return 0 num = den = 1 for i in range(1, r + 1): num = num * (n - i + 1) % p den = den * i % p return num * pow(den, p - 2, p) % pdef lucas(n, r, p): res = 1 while n > 0 or r > 0: ni, ri = n % p, r % p if ri > ni: return 0 res = res * ncr_small(ni, ri, p) % p n //= p r //= p return resimport sysn, r, p = map(int, sys.stdin.readline().split())print(lucas(n, r, p))
// Lucas Theoremimport java.util.*;import java.io.*;public class Main { static long modpow(long a, long b, long m) { long res = 1; while (b > 0) { if ((b & 1) == 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } static long ncrSmall(long n, long r, long p) { if (r > n) return 0; long num = 1, den = 1; for (int i = 1; i <= r; i++) { num = num * (n - i + 1) % p; den = den * i % p; } return num * modpow(den, p - 2, p) % p; } static long lucas(long n, long r, long p) { long res = 1; while (n > 0 || r > 0) { long ni = n % p, ri = r % p; if (ri > ni) return 0; res = res * ncrSmall(ni, ri, p) % p; n /= p; r /= p; } return res; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); long n = Long.parseLong(st.nextToken()); long r = Long.parseLong(st.nextToken()); long p = Long.parseLong(st.nextToken()); System.out.println(lucas(n, r, p)); }}
stdin
7 3 5
결과
1
stdin
1000000000000000000 500000000000000000 3
결과
0
복잡도
항목
값
시간
O(log_p N) 자릿수 순회
공간
O(1) (전처리 없음) / O(p) (팩토리얼 전처리)
p 제한
소수여야 함
전처리로 p 이하 팩토리얼과 역원을 미리 구하면 각 자릿수 조합이 O(1). 자릿수 개수는 log_p N.
변형
변형
설명
팩토리얼 전처리 버전
p 가 작으면 O(p) 전처리 후 각 자릿수 O(1)
nCr mod p^k (Lucas 확장)
Granville 의 일반화. p 소수 거듭제곱에 대해서도 동작
DP + Lucas
Catalan 수 등에 Lucas 적용
음이항 계수
확장 Lucas (n < 0 지원)
함정
1. ri > ni 이면 0
if (ri > ni) return 0; // 빼먹으면 잘못된 값
p 진수에서 r 의 자릿수가 n 의 자릿수보다 크면 그 조합은 0.
2. p 가 소수가 아닐 때
Lucas 정리는 p 가 소수일 때만 성립. 합성수 mod 에서는 확장 Lucas (Granville) 또는 중국인 나머지 정리 필요.
3. n == 0 or r == 0
r=0 이면 1 반환. 반복문에서 n, r 이 0 이 될 때까지 도므로 자동 처리됨 (n_i=0, r_i=0 → 0C0=1).
4. 64비트 오버플로우
곱셈에 res * nCr_small 에서 long long 범위 내. p^2 이 2^63 미만인지 확인.
💬 댓글