250x250
반응형
Notice
Recent Posts
Recent Comments
Link
N
(SWEA c++)5607. [Professional] 조합 본문
728x90
반응형
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
페르마의 소정리를 이용하여 조합을 구하는 문제.
페르마의 소정리는 아래 블로그를 통해 많은 도움을 얻었다.
SWEA D3] 5607. [Professional] 조합 - 페르마의 소정리
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGK...
blog.naver.com
DP를 이용하여 factorial을 모두 구해놓은 뒤 페르마의 소정리에 맞춰 답을 구하면 된다.
#include <iostream>
#include <vector>
using namespace std;
long long MOD = 1234567891;
long long fac[1000001] = {1, 1, };
long long fermat(int N, long long mod)
{
if(mod == 0)
return 1;
long long tmp = fermat(N, mod / 2);
long long ans = (tmp * tmp) % MOD;
if(mod % 2 == 0)
return ans;
else
return (N * ans) % MOD;
}
int main(void)
{
int t;
cin >> t;
//Factorial 미리 구하기
for(int i = 2; i <= 1000000; i++)
fac[i] = (fac[i - 1] * i) % MOD;
for(int i = 1; i <= t; i++)
{
int N, R;
long long ans, a;
cin >> N >> R;
a = fermat((fac[R] * fac[N - R]) % MOD, MOD - 2);
ans = (fac[N] * a) % MOD;
cout << "#" << i << " " << ans << endl;
}
return 0;
}
728x90
반응형
'SW Expert Academy' 카테고리의 다른 글
(SWEA c++)1206. [S/W 문제해결 기본] 1일차 - View (0) | 2020.10.06 |
---|---|
(SWEA c++)5603. [Professional] 건초더미 (0) | 2020.10.05 |
(SWEA c++)2001. 파리 퇴치 (0) | 2020.09.28 |
(SWEA c++)2005. 파스칼의 삼각형 (0) | 2020.09.28 |
(SWEA c++)2007. 패턴 마디의 길이 (0) | 2020.09.28 |