모듈로 곱셈 역원2 [백준 13977] 이항 계수와 쿼리 [C] 풀이 "백준 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] .. 2021. 8. 28. [백준 11401] 이항 계수 3 [C] 풀이 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", .. 2021. 8. 28. 이전 1 다음
