使用模反元素的概念來計算nCr的％MOD

我使用的關係（N + 1）的Cr =（NCR）*（N 1）/（N + 1-R）

我必須遍歷對於n保持恆定ř的不同值的循環。

llu fact=1; 
/*The loop begins from i>=M+1 */ 
fact=(fact*(i-1)*modInverse(i-M,MOD))%MOD; // Single statement executed during each iteration of loop 


    Here I'm calculating (i-1)C(M-1) 
    Here M and MOD are constant values 
    MOD=1000000009 and llu refers to unsigned long long

我在做什麼到底是

(n+1)Cr % MOD = [ (nCr) * (n+1) * modInverse(n+1-r) ] % MOD

這裏modInverse calulates模反元素如按照如下定義：

llu modPow(llu a, llu x, llu p) 
{ 
    //calculates a^x mod p 
    llu res = 1; 
    while(x > 0) 
    { 
     if(x % 2 != 0) 
     { 
      res = (res * a) % p; 
     } 
     a = (a * a) % p; 
     x /= 2; 
    } 
    return (res%MOD); 
} 
llu modInverse(llu a, llu p) 
{ 
    //calculates the modular multiplicative of a mod m assuming p is prime 
    return modPow(a, p-2, p); 
}

現在的問題是，我沒有變n的大數值nCr的正確值（次序爲10^6）。我的方法是

(n+1)Cr % MOD = [ (nCr) * (n+1) * modInverse(n+1-r) ] % MOD

從概念上說錯了嗎？

來源

2014-03-13 CPPCoder

我正在研究與（a * b）％c =（（a％c）*（b％c））％c相同的想法 – CPPCoder

您是否嘗試過在添加後綴ULL或LLU時除以2 ？ x/= 2LLU; 通常編碼時，如果不指定編譯器的文字類型，會帶來這種截斷問題。 –

是的，底部的公式在數學上是合理的。

然而，通過採取模前做2次乘法，這會增加溢出問題的機會。

例如，MOD是O（10^10），以便modInverse也O（10^10）。如果n是O（10^6），那麼產品是O（10^26），它是O（2^86）並且會導致uint64溢出，並給你錯誤的答案。考慮改爲：

(n+1)Cr % MOD = [ ([(nCr) * (n+1)] % MOD) * modInverse(n+1-r) ] % MOD

您可能也有興趣我的回答this suspiciously similar question。

來源

2015-04-22 04:11:42

使用模反元素的概念來計算nCr的％MOD

回答

相關問題