이항게수와 관련된 PS를 하다가 범위가 큰 n과 범위가 큰 r에 대해서 nCr의 일의 자리 수를 구해야하는 일이 생겼다. 일반적인 콤비네이션 계산(O(n))을 하고 일의 자리수를 구하면 시간초과가 나서 다른 방법이 필요했다. 이 포스팅에서는 이와 관련된 내용을 적어보려고 한다. 1. 조합을 계산하는 일반적인 방법 가장 쉬운 방법으로는 정의식대로 n!, (n-r)!, r!을 모두 계산해주고 연산해주는 것이다. 하지만 n과 r이 조금만 커져도 계산 시간이 오래걸리고 PS에서는 정수형 범위나 심지어는 long long 범위까지 넘어갈 수 있기 때문에 좋지 않은 방법이다. int factorial(int n) { int output = 1; for(int i = 1; i >n>>p; k1 = p_digit(n,..