BOJ 16565 N포커

N포커
(http://boj.kr/16565)

카드가 13종류밖에 안 되니 포함배제의 원리로 구해보자.
구해야 하는 것은 한 종류라도 \(4\)가지가 모인 경우이다.
이는 한 종류를 \(4\)가지 모은 경우 - 두 종류를 \(4\)가지 모은 경우 + 세 종류를 \(4\)가지 모은 경우 - 네 종류를 \(4\)가지 모은 경우 + ... 이다.

즉 홀수개를 모은 경우의 수는 더해주고 짝수개를 모은 경우의 수는 빼주면 된다.

\(n\)개를 뽑아 \(i\)종류를 \(4\)가지 모은 경우의 수는 조합으로 생각해 볼 수 있다.
카드 \(4i\)개는 모아야하니 정해진 부분이고, \(4i\)개를 제외한 나머지 \(n-4i\)개는 아무렇게나 들어가도 된다.
정해진 부분은 \(13\)종류의 카드 중 \(i\)개를 고르는 것이니 \(_{13}\mathrm{C}_i\)와 같다.
\(4i\)개가 정해져있다고 치면, 나머지를 넣는 경우의 수는 \(_{52-4i}\mathrm{C}_{n-4i}\)와 같다.
그러니 \(n\)개를 뽑아 \(i\)종류를 \(4\)가지 모은 경우의 수는 \(_{13}\mathrm{C}_i \times _{52-4i}\mathrm{C}_{n-4i}\)이다. 이걸 홀수, 짝수를 나눠 계산하면 된다.

#include <bits/stdc++.h>
 
const int r = 10007;
 
int c[53][53];
 
int main() {
    for (int i = 0;i <= 52;++i)
        c[i][0] = 1;
    for (int i = 1;i <= 52;++i)
        for (int j = 1;j <= 52;++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % r;
 
    int n;
    scanf("%d", &n);
    int ans = 0;
    for (int i = 1;i <= 13 && n - 4 * i >= 0;++i) {
        if (i % 2 == 1)
            ans = (ans + c[52 - 4 * i][n - 4 * i] * c[13][i] % r) % r;
        else
            ans = (ans - c[52 - 4 * i][n - 4 * i] * c[13][i] % r + r) % r;
    }
 
    printf("%d", ans);
 
    return 0;
}