16565 N포커

주간 연습때 무조건 골드 두 문제만 해치운다고 마음먹고 고민했는데 엄... 음..... 아무리해도 못 풀겠다. 그래서 머리 굴리다가 결국 다른 사람 풀이를 참고했다. 

 

으! 수학이잖아

 

포함 배제의 원리를 쓴다고 한다. 찾아보니 전부 더하고 교집합 빼고 더하고 하는 그거인 것 같다. 

 

그래서 한 종류를 4가지 모은 경우 - 두 종류를 4가지 모은 경우 + 3종류 - 4종류 ... 이렇게 푼다. 

 

n개를 뽑아 i 종류를 4가지 모은 경우의 수는 조합으로 구할 수 있다. 13종류 중 i개를 골라야 하니 13Ci

 

나머지 카드를 뽑는 경우는 4i개를 모아야 하니 나머지 n - 4i개는 아무렇게나 들어가도 된다. 52 - 4i C n - 4i와 같다. 

 

그래서 경우의 수는 13Ci * 52 - 4i C n - 4i

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MOD 10007

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int nCk[53][53];

int main() {
    int n;
    scanf("%d", &n);
    
    for (int n = 0; n <= 52; n++) {
        nCk[n][0] = 1; 
        nCk[n][n] = 1;
        for (int k = 1; k < n; k++) {
            nCk[n][k] = nCk[n-1][k-1] + nCk[n-1][k]; 
            nCk[n][k] %= MOD;
            nCk[n][n-k] = nCk[n][k];
        }
    }
    int ans = 0;
    for (int i = 4; i <= n; i += 4) {
        if ((i / 4) % 2 == 1)
            ans = (ans + nCk[13][i/4] * nCk[52 - i][n - i]) % MOD;
        else
            ans = (ans - nCk[13][i/4] * nCk[52 - i][n - i]) % MOD;
    }
    if (ans < 0)
        ans += MOD;
        
    printf("%d\n", ans);
    return 0;
}