큰 숫자를 가진 분수의 모듈러스를 계산하십시오.

Question

두 개의 큰 숫자 (< 10^9) n과 m이 있습니다. 대답이 너무 크면 (10^9+7)에서 모듈러스를 얻어야합니다. [(n-1+m)!]/[(n-1)!*m!] 을 계산해야합니다. (예 : n이 mod보다 너무 큰 경우 n % mod).

다음과 같이 계산했습니다.

long up=1; 
    for (long i = a+b-1; i>=Math.max(a, b); i--) { 
     up*=i%mod;    
    } 
    up=up%mod; 
    long down=1; 
    for (long i = Math.min(a, b); i>0; i--) { 
     down*=i%mod;    
    } 

다음

System.out.println((up%mod/down%mod)%mod); 

이 정확이 접근됨에 응답을 출력 (I는 상반부와 하반부를 개별적으로 계산). 올바른 출력을 제공합니까? 내가 (a*b*c)%d == [(a%d)*(b%d)*(c%d)]%d

그래서 [a/b]%d을 계산하는 그런 어떤 방법이 (내가 틀렸다면 정정 해줘을) 알고

? 이 재귀 위

(n - 1 + m, m) % MOD = ((n - 2 + m, m - 1) % MOD + (n - 2 + m, m) % MOD) % MOD 

사용됩니다

Answer 1

(a/b) % c != ((a%c)/(b%c) % c) 

대신 결과를 얻기 위해 계수 귀하의 경우

(n, k) = (n - 1, k - 1) + (n - 1, k) 

을 계산하는 binomial coefficient의 재귀 공식을 사용합니다.