1

这是使用费马小定理计算 nCr % P 的代码

long long power(long long x, long long y, long long p) 
{ 
    long long res = 1;      // Initialize result 

    x = x % p;  // Update x if it is more than or 
            // equal to p 

    while (y > 0) 
    { 
    // If y is odd, multiply x with result 
        if (y & 1) 
           res = (res*x) % p; 

         // y must be even now 
         y = y>>1; // y = y/2 
         x = (x*x) % p; 
    } 
    return res; 
} 

// Returns n^(-1) mod p 
long long modInverse(long long n, long long p) 
{ 
    return power(n, p-2, p); 
} 

// Returns nCr % p using Fermat's little 
// theorem. 
long long nCrModPFermat(long long n, long long r, long long p) 
{ 
    // Base case 
   if (r==0) 
       return 1; 

    // Fill factorial array so that we 
    // can find all factorial of r, n 
    // and n-r 

    long long fac[n+1]; 
    fac[0] = 1; 
    for (long long i=1 ; i<=n; i++) 
        fac[i] = fac[i-1]*i%p; 

     return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[n-r], p) % p) % p; 
}

为了优化代码，我预先计算了fac[]数组并将其作为参数传递给nCrModPFermat()函数：

long long nCrModPFermat(long long n, long long r, long long p,long long fac[])
{
  //same code as above
}

int main()
{
    long long  fac[2001];
    fac[0] = 1;
    for (long long  i=1 ; i<=2000; i++)  //calculating factorials upto 2000
        fac[i] = fac[i-1]*i%M;
    for(i=0;i<2000;i++)
        nCrModPFermat(2000,i,M,fac);
}

我的输出与预期不符。奇怪的是，当我fac[]全局声明数组并通过调用函数计算高达 2000 的阶乘时：

long long  fac[2001];
void funci()
{
    fac[0] = 1;
    for (long long  i=1 ; i<=2000; i++)  //calculating factorials upto 2000
        fac[i] = fac[i-1]*i%M;
}

long long nCrModPFermat(long long n, long long r, long long p)
{
    //same code as above
}

int main()
{
    funci();
    for(i=0;i<2000;i++)
        nCrModPFermat(5000,i,M); 
}

我得到了预期的输出。我只想知道为什么传递数组会导致代码出错

4

0 回答 0