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

Question

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

nCr = n!/(n-r)!*r! %M

也就是说，nCr = n! * (逆因子(n-r)*逆因子(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;

   }

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

modular multiplicative inverse of an number for calculating nCr % 10000007 (combination)

algorithm

data-structures

combinations

modulo

factorial