组合数

题意

求对取模的结果。

解法1

可以一项一项地求出每一项的值，再逐项加起来，求每一项的组合数可以用以下式子推出：

根据费马小定理

 

代码

class Solution {
public:
    /**
     * 
     * @param n long长整型 
     * @return long长整型
     */
    static const long long MOD = 1e9+7;//模数
    long long qpow(long long a,long long b)//快速幂
    {
         if(b==0)return 1;
         long long tmp=qpow(a,b>>1);
         tmp=tmp*tmp%MOD;
         if(b&1)tmp=tmp*a%MOD;
         return tmp;
    }
    long long combinatorial(long long n) {
        // write code here
       long long c=1;//C(n,0)=1
       long long ans = 0;
       for(long long i=1;i<=n;i++)
       {
          c=c*(n-i+1)%MOD*qpow(i,MOD-2)%MOD;
          ans=(ans+i*c%MOD)%MOD;
    }
   return ans;
 }
};

解法2

以上解法复杂度过高，无法通过所有测试数据。
由二项式定理：

令  ，得

上式对进行求导得

再令得

于是我们只需将对取模只可。
时间复杂度：
空间复杂度：

代码

class Solution {
public:
    /**
     * 
     * @param n long长整型 
     * @return long长整型
     */
    static const long long MOD = 1e9+7;//模数
    long long qpow(long long a,long long b)//快速幂
    {
         if(b==0)return 1;
         long long tmp=qpow(a,b>>1);
         tmp=tmp*tmp%MOD;
         if(b&1)tmp=tmp*a%MOD;
         return tmp;
    }
    long long combinatorial(long long n) {
        // write code here
       return n%MOD*qpow(2,n-1)%MOD;
 }
};