조합론3 [알고리즘] 파스칼 삼각형을 활용한 조합 계산 1. 파스칼 삼각형 2. 소스 코드(C++)int Combination[53][53];// 조합 계산 함수int cal_combination(int n, int r) { if (Combination[n][r]) return Combination[n][r]; // 이전에 계산해놓은 값이 있으면, 바로 반환 else if (n == r || r == 0) Combination[n][r] = 1; // n=r 이거나, r = 0일 때, 1 반환 else { Combination[n][r] = cal_combination(n - 1, r) + cal_combination(n - 1, r - 1) % MOD; // nCr = n-1Cr + n-1Cr -1 } return Combination[n][r];} 2024. 9. 5. [백준 C++] 16565번: N포커 1. 문제https://www.acmicpc.net/problem/16565 2. 알고리즘 분류수학다이나믹 프로그래밍조합론포함 배제의 원리 3. 소스 코드#include #define MOD 10007using namespace std;int N;int Combination[53][53];// 조합 계산 함수int cal_combination(int n, int r) { if (Combination[n][r]) return Combination[n][r]; // 이전에 계산해놓은 값이 있으면, 바로 반환 else if (n == r || r == 0) Combination[n][r] = 1; // n=r 이거나, r = 0일 때, 1 반환 else { Combination[n][r] = cal_com.. 2024. 9. 5. [백준 C++] 15824번: 너 봄에는 캡사이신이 맛있단다 1. 문제https://www.acmicpc.net/problem/15824 2. 알고리즘 분류수학정렬조합론분할 정복을 이용한 거듭제곱 3. 소스 코드#include #include #define MAX_N 300000using namespace std;typedef long long ll;ll scovile[MAX_N];ll MOD = 1000000007;// binary exponentiation 알고리즘ll binpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a) % MOD; a = (a * a) % MOD; b >>= 1; } return res;}int main() { ios_base::sync_with_stdio(fa.. 2024. 6. 15. 이전 1 다음
