이항계수( binomial coefficient), 조합(combination)

이항계수 ${n}\choose{k}$는 $_nC_k$ 조합과 동일하다.

구하는 방법은 다음과 같다.

$$_nC_k = {n!\over{k!(n-k)!}}$$

예를 들어 바구니에 든 10개의공 중에서 순서에 상관없이 3개의 공을 꺼내는 경우의 수를 구하라고 하면 다음처럼 구하면 된다.

$$_{10}C_k = {{10}!\over{3!7!}} = {{{10}\times 9\times 7}\over{1\times 2\times 3}} = 120$$

브루트포스

이를 브루트포스로 구현하면 다음과 같이 되는데

    long long fact[100] = {};
    fact[0] = fact[1] = 1;
    for(int i=2;i<100;i++)fact[i] = i*fact[i-1];
    int n = 10, k = 3;
    printf("%lld\n", fact[n]/(fact[k]*fact[n-k]));

일단 중간에 들어가는 factorial자체가 다음과 같이 n이 20을 넘어가면 long long 범위를 초과해 버려서 n이 20이하일 때만 사용할 수 있는 방법이다.

fact[1]:1
fact[2]:2
fact[3]:6
fact[4]:24
fact[5]:120
fact[6]:720
fact[7]:5040
fact[8]:40320
fact[9]:362880
fact[10]:3628800
fact[11]:39916800
fact[12]:479001600
fact[13]:6227020800
fact[14]:87178291200
fact[15]:1307674368000
fact[16]:20922789888000
fact[17]:355687428096000
fact[18]:6402373705728000
fact[19]:121645100408832000
fact[20]:2432902008176640000
fact[21]:-4249290049419214848

$O(n^2)$ 파스칼의 삼각형 점화식 이용

다음처럼 dp solution을 적용하면 n이 대략 50근방일 경우 해결 가능하다.

(n이 100이 넘어서 예를 들어 $_{100}C_{50}$만 되어도 값이 100891344545564193334812497256 이렇게 커져서 long long 범위를 초과해 버린다.

이럴 경우 이 소스코드를 참고해서 bigint를 쓰면 쉽게 해결할 수도 있다)

const int MAX = 50;
long long C[MAX+1][MAX+1] = {};
int main(void)
{
    C[0][0]=1;
    for(int i=1;i<=MAX;i++){
        C[i][0]=1;
        for(int j=1;j<=MAX;j++)
            C[i][j] = C[i-1][j-1]+C[i-1][j];
    }

    printf("%lld\n", C[10][3]);
    return 0;
}

위 코드를 이해하려면 다음 관계 식을 알아야 하는데,

$$_nC_k=_{n-1}C_{k-1}+_{n-1}C_k$$

수학적으로 증명하는건 오히려 어렵지 않고, 개념적으로 이해하기는 조금 까다로울 수 있는데.. 대부분의 인터넷자료에서 설명하기로는 다음과 같다.

특별한공을 하나 마킹하고, 이공을 포함하는 경우와 포함하지 않는 경우로 나눠서 생각하면

정답은 (포함하는경우)+(포함하지 않는 경우)가 될 것이다.

포함하는 경우에는 마킹한거는 이미 공을 골라놓은 셈이니

n-1개에서 k-1개를 뽑는게 될테니까 $_{n-1}C_{k-1}$이 될 것이고,

포함하지 않은 경우에는 마킹한거를 빼놓고 k개를 골라야 하니 

n-1개에서 k개를 뽑는게 될테니까 $_{n-1}C_k$가 될 것이다.

뭐 적당히 납득할만한 설명인것 같다는 생각은 든다.

$O(n\log n)$ 페르마의 소정리

n의 범위가 더 커질 경우, 보통 modulo 연산과 함께 나오는 경우가 많다.

예를 들어 이 문제와 같이 N이 매우클때 결과값을 10,007로 나눈 나머지를 구하라는 문제가 있다고 하자.

mod연산의 경우 덧셈, 뺄셈, 곱셈에 대해서는 자유롭게 중간 중간 mod를 취해줘도 결과가 같지만 나눗셈에 대해서는 그렇지 않은데,

하필이면 이항계수 계산식에는 나눗셈이 들어가며 그 식을 한줄로 나타내 보면 다음과 같다.

$$ [n! / (k!(n-k)!)]  \% 10,007$$

그런데 만약 $(k!(n-k)!)$의 역원인 $(k!(n-k)!)^{-1}$을 구하게 되면 다음처럼 나눗셈이 곱셈으로 바뀌어서 mod연산을 취할 수 있게 된다.

$$[n! \times (k!(n-k)!)^{-1}]  \% 10,007 = [n!\%10,007 \times (k!(n-k)!)^{-1}\%10,007]  \% 10,007 $$

근데 언뜻들으면 말장난처럼 보일것이다. 왜냐하면 저 역원은 당연히 1보다 작은 분수처럼 보이기 때문이다.

하지만 실제 역원이 아닌 모듈러 연산에 대한 역원은 분수가 아닐 수 있다. 다음을 보자.

$$k!(n-k)! \times x \equiv 1(\mod 10,007)$$

위 식에서 x가 바로 k!(n-k)!의 모듈러 연산에 대한 역원이 되는데, k!(n-k)!에다가 어떤 자연수를 곱하고 모듈러 한 이후에 나온 나머지가 1이기만 하면 되는 조건이기 때문에 충분히 분수가 아니라 자연수가 될 수 있음을 간파할 수 있다.

그럼 분수가 아닌 자연수인 역원은 어떻게 구할 수 있을까?

페르마의 소정리는 다음과 같다.

p가 소수이고 a가 p가 서로소이면

$$a^{p-1} \equiv 1(\mod p)$$

이를 좀 변형하면

$$a \times a^{p-2} \equiv 1(\mod p)$$

이렇게 되고, 신기하게도 a의 모듈러 연산에 대한 역원이 바로 $a^{p-2}$가 됨을 알 수 있다.

$a^{p-2}$를 빠르게 구하는 방법은 분할정복을 쓰면 되며, 나눗셈이 들어가던 원래의 식은 다음처럼 바뀐다.

$$ [n! / (k!(n-k)!)]  \% 10,007 = [n! \times (k!(n-k)!)^{-1}]  \% 10,007 = [n! \times (k!(n-k)!)^{p-2}]\%10,007$$

식을 보면 -1승을 p-2승으로 바꿔주면 되는걸 볼 수 있다.

위의 내용을 전체적으로 반영한 코드는 다음과 같다.

#define ll long long
ll f[4000001];
ll M = 1000000007;
ll pp(ll a, ll p, ll M)
{
    if(p==1) return a;
    ll b = pp(a,p/2,M);
    if(p%2==0){
        return (b*b)%M;
    }else{
        return (((b*b)%M)*a)%M;
    }
}
int main(void)
{
    int N,K;scanf("%d %d",&N, &K);
    f[0]=f[1]=1;for(int i=2;i<4000001;i++)f[i]=(i*f[i-1])%M;
    printf("%lld\n", (f[N]*pp((f[K]*f[N-K])%M,M-2,M))%M);

    return 0;
}

약분하기

modulo가 없고 n의 값이 큰 경우에 사용할 수 있는 방법인데 이것도 재밌는 방법이다.

$$_{10}C_{3} = {{10\times9\times8}\over{1\times2\times3}}$$ 

이런식이 되는데..

10곱하고 1로 나누고 9곱하고 2로나누고 8곱하고 3으로 나누고 이런식으로 구하자는 것 ㅋ

한가지 걱정되는것은 이렇게 했을때 순간적으로라도 나눈값이 정수가 아닌 경우가 생기면 망하는건데

증명은 모르겠지만 실제로 그런경우는 없나보다.

코드는 다음처럼 심플하다.

        int n,m;scanf("%d %d",&n, &m);

        m = min(m,n-m);
        long long r = 1;
        long long div = 1;
        while(m--)
        {
            r*=n--;
            r/=div++;
        }
        printf("%lld\n", r);

n의 범위가 커도 동작하는 대신 쿼리한번에 걸리는 시간이 좀 있다보니 일반적인 경우는 n이 크지만 않다면 dp솔루션이 더 활용도가 높다.