用于计算nCr％10000007（组合）的数字的模乘逆数

Question

[我正在尝试计算nCr％M。所以我正在做的是

nCr = n！/（n-r）！* r！ ％M

换句话说，nCr = n！ *（inverseFactorial（n-r）* inverseFactorial（r））。所以我正在预先计算范围从1到10 ^ 5的数字的阶乘和逆因子的值。基本上，我正在尝试实现第一个答案。

https://www.quora.com/How-do-I-find-the-value-of-nCr-1000000007-for-the-large-number-n-n-10-6-in-C

这是我的代码。

        //fill fact
        fact[0]=1;
        for(int i=1;i<100001;i++){
            fact[i]=fact[i-1]*i%1000000007;
            //fact[i]=fact[i]%1000000007;
        }

        //fill ifact - inverse of fact
        ifact[0]=1;
        for(int i=1;i<100001;i++){
            ifact[i] = ifact[i-1]*inverse(i)%1000000007;
            //ifact[i]=ifact[i]%1000000007;
        }

方法是

public static long fastcomb(int n,int r){

        long ans = ifact[r]*ifact[n-r];
        System.out.println(ifact[r]);
        System.out.println(ifact[n-r]);
        ans = ans%1000000007;
        ans=ans*fact[n];
        System.out.println(fact[n]);
        ans = ans%1000000007;
        return ans;

    }


 public static int modul(int x){
        x = x%1000000007;
        if(x<0){
            x+=1000000007;
        }
        return x;
    }

public static int inverse(int x){
    int mod = modul(x);
    if(mod==1){
        return 1;
    }

    return modul((-1000000007/mod)*(ifact[1000000007%mod]%1000000007));

}

我不确定我要去哪里错了？请帮助我做错了，因为ifact [2]显示500000004。

Answer 1

这里是乘法逆的费马小定理实现。我对其进行了测试，并且可以正常工作。

   static long modInverse(long a, long m)
   {
         return power(a, m - 2, m);
   }

   // To compute x^y under modulo m
   static long power(long x, long y, long m)
   {
      if (y == 0)
         return 1;

      long p = power(x, y / 2, m) % m;
      p = (p * p) % m;

      if (y % 2 == 0)
         return p;
      else
         return (x * p) % m;
   } 

我正在研究nCr mod M，您不需要该数组即可找到它。

找到nCr mod m的以下实现，请使用您的值进行检查，请记住m应该是此方法的质数。

   static long nCr_mod_m(long n, long r, long m)
   {
      if(n-r < r) r = (n-r);    //  since nCr = nC(n-r)

      long top_part = n, bottom_part=1;

      for(long i=1; i<r; i++)
         top_part = (top_part*(n-i)) % m;

      for(long i=2; i<=r; i++)
         bottom_part = (bottom_part * modInverse(i, m))%m;

      return (top_part*bottom_part)%m;

   }