이항 계수 4 (백준 11402)

안녕하세요. 오늘은 조합을 공부할 거예요.

문제

https://www.acmicpc.net/problem/11402

아이디어

뤼카의 정리라는것이 있습니다.
임의의 소수 p에 대하여 n을 p진법으로 나타냈을때 총 N자리의 수라면 모든 자리의 수에 대하여 n의 그 자리의 수를 x, k의 그 자리의 수를 y라고하면 (nCk)와 (xCy의 곱)은 p로 나눈 나머지가 같습니다. 이때 k에서 자릿수를 넘어가면 0으로 간주하며, x<y의 경우에는 0으로 간주합니다. 이를 구현하면 됩니다. 설명이 이해가 안되면 위키백과 ㄱㄱ (ㅋㅋㅋ)

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll comb[2020][2020] = { 0 };

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll N, K, M;
	cin >> N >> K >> M;

	comb[0][0] = 1;
	for (ll i = 1; i < M; i++)
	{
		for (ll j = 0; j <= i; j++)
		{
			if (j == 0) comb[i][j] = 1;
			else comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % M;
		}
	}

	ll mul = 1;
	while (N && K)
	{
		if (N % M >= K % M) mul *= comb[N % M][K % M];
		else mul = 0;
		mul %= M;
		N /= M; K /= M;
	}

	cout << mul;
}

감사합니다.