0과 1의 쉼터

풀이 "백준 11401, 이항 계수 3"보다 N의 범위가 작은 문제이다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long N, K, A = 1, B = 1; scanf("%d %d", &N, &K); for (int i = N; i > N-K; i--) A = A*i %MOD; for (int i = K; i >= 2; i--) B = B*i %MOD; N = 1, K = MOD-2; while (K){ if (K & 1) N = N*B %MOD; K >>= 1; B = B*B %MOD; } printf("%d", A*N %MOD); } 출처 및 참고자료 15791번: 세진이의 미팅 모태 솔로인 세진이는 이번에는 꼭 여자친구를 사귀어야겠다는 마음으..

풀이 "백준 11401, 이항 계수 3"의 확장 문제이다. M개의 N과 K에 대해 이항 계수를 계산해야 하므로, 미리 4e6까지의 factorial과 역원을 구해주면 된다. 소스코드 #include #define ll long long #define MAX 4000001 const int MOD = 1e9+7; int A[MAX] = {1}, B[MAX]; int pow(ll a, int b){ ll result = 1; while (b){ if (b & 1) result = result*a %MOD; b >>= 1; a = a*a %MOD; } return result; } int main(){ for (ll i = 1; i < MAX; i++) A[i] = A[i-1]*i %MOD; B[MAX-1] ..

풀이 "백준 11401, 이항 계수 3"보다 N의 범위가 작은 문제이다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long N, K, A = 1, B = 1; scanf("%d %d", &N, &K); for (int i = N; i > N-K; i--) A = A*i %MOD; for (int i = K; i >= 2; i--) B = B*i %MOD; N = 1, K = MOD-2; while (K){ if (K & 1) N = N*B %MOD; K >>= 1; B = B*B %MOD; } printf("%d", A*N %MOD); } 출처 및 참고자료 16134번: 조합 (Combination) \(\begin{pmatrix}N\\R\end{p..

풀이 MOD가 소수이기 때문에, A = N! - (N-K)!와 B = K!를 MOD로 나누며 구하고, Fermat’s little theorem를 이용해 ( A* B^(MOD-2) )%MOD를 구하면 된다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long N, K, A = 1, B = 1; scanf("%d %d", &N, &K); for (int i = N; i > N-K; i--) A = A*i %MOD; for (int i = K; i >= 2; i--) B = B*i %MOD; N = 1, K = MOD-2; while (K){ if (K & 1) N = N*B %MOD; K >>= 1; B = B*B %MOD; } printf("%d", ..

풀이 지문이 어마무시하게 길면서 Fermat’s little theorem에 대해 설명이 친절한 문제이다. 요점은 다음과 같다. M개의 N과 S에 대해 S*N^(MOD-2)의 합들을 MOD로 나눈 나머지를 구하면 된다. 단, N^(MOD-2)를 구하는 과정에서 수가 너무 커지므로 중간과정마다 MOD로 나누어줘야 한다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long sum = 0, N; int M, S; scanf("%d", &M); while (M--){ scanf("%d %d", &N, &S); long long temp = 1, k = MOD-2; while (k){ if (k & 1) temp = temp*N %MOD; k >>= 1; N ..