빠른 집합1 조합의 소수 모듈러 값 빠르게 구하기 (n C m % p) https://ryulstory.tistory.com/62 페르마 소정리에 따르면 p가 소수인 경우 a^(p-1) = 1 (mod p) 1/a mod p == a^(p-2) 즉 다음을 만족함 (a*b) % p = (a%p) * (b%p) (a/b) % p = (a%p) * (b^(p-2) % p) nCk (mod p) = n! /(k! * (n-k)!) (mod p) = (n! mod p) * ((k! * (n-k)!)^(p-2) mod p ) 다음 두 배열을 전처리해준다. O(n) fac[x] : x! % MOD fac_inv[x] : (x!)^(-1) %MOD -> n * inverse(n!) = inverse((n-1)!) 를 이욯 O(1)에 nCm % p 를 구할 수 있다. const ll MOD.. 2020. 3. 10. 이전 1 다음