[BOJ 11402] 이항 계수 4

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

11402번: 이항 계수 4

 

- 문제 요약

 

자연수 N과 정수 K가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 M으로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

이 문제는 뤼카의 정리를 그대로 구현해서 풀어주면 됩니다.

https://ko.wikipedia.org/wiki/%EB%A4%BC%EC%B9%B4%EC%9D%98_%EC%A0%95%EB%A6%AC

뤼카의 정리 - 위키백과, 우리 모두의 백과사전

뤼카의 정리의 계산 방법을 간단하게 요약하면 아래와 같습니다.

 

1. N과 K를 M진수로 변환합니다.

2. M진수로 변환된 N과 K로 nCk를 계산합니다. (조합)

3. nCk를 M으로 모듈러 연산을 해줍니다.

 

 

- 코드 작성

 

//save

#include<bits/stdc++.h>
using namespace std;

#define MAX 2001
typedef long long ll;
ll n,k,arr[MAX][MAX],result=1;
int m,mn;
vector<int>N,K;

vector<int> luca(ll val,int mod){
	vector<int>ret;
	while(val>0){
		int w=val%mod;
		ret.push_back(w);
		val/=mod;
	}
	return ret;
}

ll jo(int nn,int kk){
	if(nn<kk){
		return 0;
	}
	if(nn/2<kk){
		kk=nn-kk;
	}
	ll &ret=arr[nn][kk];
	if(ret!=-1){
		return ret;
	}
	if(kk==0){
		return ret=1;
	}
	else if(kk==1){
		return ret=nn;
	}
	return ret=(jo(nn-1,kk-1)+jo(nn-1,kk))%m;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL); 
	cin>>n>>k>>m;
	memset(arr,-1,sizeof(arr));
	N=luca(n,m);
	K=luca(k,m);
	mn=min(N.size(),K.size());
	for(int i=0;i<mn;i++){
		int nn=N[i];
		int kk=K[i];
		result*=jo(nn,kk);
		result%=m;
	}
	cout<<result;
}

코드 제출 결과