https://www.acmicpc.net/problem/11051
자연수 N과 정수 K가 주어졌을 때 이항 계수 nCk
를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)
nCk를 10,007로 나눈 나머지를 출력한다.
// 11051번 : 이항 계수 2
#include <stdio.h>
#define mod 10007
#define MAX 1001
int dp[MAX][MAX];
void fibo(int n, int k)
{
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= k; j++)
{
if (i == j || j == 0)
{
dp[i][j] = 1;
}
else
{
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
}
}
}
}
int main()
{
int n, k;
scanf("%d%d", &n, &k);
fibo(n, k);
printf("%d\n", dp[n][k]);
return 0;
}