Boj 16565) N포커

Binomial Coefficient

백준 16565

설명

조합관련 성질

\[\begin{multline} {}_n \mathrm{ C }_k = \frac{n!}{k! (n-k)!} \\ \\ \shoveleft \shoveleft = \frac{(n-1)! \times n}{k! (n-k)!} \\ \\ \shoveleft \shoveleft = \frac{(n-1)! \times ( (n-k) + k ) }{k! (n-k)!} \\ \\ \shoveleft \shoveleft = \frac{(n-1)!}{k! (n-k-1)!} + \frac{(n-1)!}{(k-1)! (n-k)!} \\ \\ \shoveleft \shoveleft = \frac{(n-1)!}{k! (n-1-k)!} + \frac{(n-1)!}{(k-1)! (n-1-(k-1)!} \\ \\ \shoveleft \shoveleft = {}_{n-1} \mathrm{ C }_k + {}_{n-1} \mathrm{ C }_{k-1} \\ \\ \shoveleft \end{multline}\]

를 이용안하면 오버플로우 감당 못함.

포함배제

• 포카드로 카드 4개를 뽑기 위해 13개의 숫자 중 하나로 색깔별로 카드 4개를 뽑음
• 그리고 나머지 카드들로 카드를 뽑음.
• 그런데 나머지 카드에서도 포카드가 생길 수 있으니 이 경우를 빼줘야 함.
• 이 경우를 구하는 걸 위의 방법대로 하면 중복되는 경우가 없을 때 까지 재귀를 돌려야함.

15개를 뽑는다고 하면

\[\begin{multline} {}_{13} \mathrm{ C }_{1} \times {}_{48} \mathrm{ C }_{11} - ( {}_{13} \mathrm{ C }_{2} \times {}_{44} \mathrm{ C }_{7} - ( {}_{13} \mathrm{ C }_{3} \times {}_{40} \mathrm{ C }_{3} )) \end{multline}\]

시간 복잡도

범위인 O(53*53) 일듯

코드

#define MOD 10007
#define NNUM 13
int nCk[53][53];

void Init() 
{
    nCk[0][0] = 1;
    for (int n = 2; n < 53; n++)
    {
        nCk[n - 1][0] = 1; nCk[n - 1][1] = 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;
        }
    }
}

int PurePack(int n, int m)
{
	int r = nCk[NNUM][n];        // n 개의 포카드를 뽑음
    r *= nCk[(NNUM-n)*4][m-n*4]; // 나머지 카드를 뽑음
	if (m-(n+1)*4 >= 0) 
        r -= PurePack(n+1, m) ;	
	return r < 0 ? r + 10007 : r % 10007;
}

int main()
{
    Init();

    int d;
	cin >> d;
	cout << PurePack(1, d);
}