레야몬

1. 문제 M개의 자연수 N과 정수 K가 주어졌을 때 이항 계수 \(_{n}C_{k}\)를 \(1,000,000,007\)로 나눈 나머지를 구하는 프로그램을 작성하시오 - 1 - \(M(1 \leq M \leq 100,000)\) - M개의 줄 - \(N, K(1 \leq N \leq 4,000,000, 0 \leq K \leq N)\) M개의 줄에 \(_{n}C_{k}\)를 \(1,000,000,007\)로 나눈 나머지를 출력한다. 2. 재정의 X 3. 해결 방법 factorial값을 모두 저정한 다음 페르마의 소정리를 이용해 간단하게 풀면 된다. 4. 실수한 점, 개선할 점 항상 나오지만 자료형 범위 조심하자 분할 정복 사용할 때 재귀 함수를 사용하지 않고 반복문을 이용해하는 방법도 있었다. 이렇게 ..

1. 문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 nCk를 M으로 나눈 나머지를 구하는 프로그램을 작성하시오. - 1 - \(N, K, M(1 \leq N \leq 10^{18}, 0 \leq K \leq N, 2 \leq M \leq 2,000, M is prime)\) \(_{n}C_{k}\)를 \(M\)으로 나눈 나머지를 출력한다. 2. 재정의 X 3. 해결 방법 뤼카의 정리를 이용하면 간단하게 풀 수 있다. 4. 실수한 점, 개선할 점 binomial을 사용할 때 dp를 사용하지 않고 Euler's little theorem을 사용하면 0ms로 풀 수 있다. #include #include using namespace std; typedef long long ll; const int MAX..

1. 문제 \(_{n}C_{k} \% 1,000,000,007\)을 구하시오 - 1 - \(N, K(1 \leq N \leq 4,000,000, 0 \leq k \leq N)\) \(_{n}C_{k} \% 1,000,000,007\) 2. 재정의 X 3. 해결 방법 \(P = N! \% M\)을 구하기 \(S = (N-K)! \times k! \% M\) 구하기 \(S^{1,000,000,005} \% M\) 구하기 \(P \times S \% M\) 구하기 4. 실수한 점, 개선할 점 nCr을 팩토리얼로 계산할 때 반복문 하나로 줄일 수 있다. #include using namespace std; typedef long long ll; // 소수 const int mod = 1000000007; // ..

#include #include #include using namespace std; typedef long long ll; __uint128_t memo[101][101]; __uint128_t comb(int n, int r) { if(n> n >> r; res = comb(n, r); string a = ""; string f = to_string((ll) (res / (__uint128_t)pow(10, 15))); string s = to_string((ll) (res % (__uint128_t)pow(10, 15))); if(f=="0") a=s; else a=f+s; cout int 로 변.. blockdmask.tistory.com ※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격..