题目：

思路：求C(m+n-2,n-1) % 10^9 +7       (2<=m,n<= 1000000)

　　　在求组合数时，一般都通过双重for循环c[i][j] = c[i-1][j] + c[i-1][j-1]直接得到。

　　　但是m,n都很大时，就会超时。

　　　

　　　利用公式：C(n,r) = n! / r! *(n-r)!  与  a/b = x(mod M)  ->  a * (b ^ (M-2)) =x (mod M)     进行求解

 

费马小定理：对于素数 M 任意不是 M 的倍数的 b，都有：b ^ (M-1) = 1 (mod M)

a/b = x(mod M)  ->  a * (b ^ (M-2)) =x (mod M)的推导：

　　只要 M 是一个素数，而且 b 不是 M 的倍数，就可以用一个逆元整数 b’，通过 a / b = a * b' (mod M)，来以乘换除。

　　a/b = x(mod M)

　　a / b = a / b * (b ^ (M-1)) = a * (b ^ (M-2)) = x(mod M)

　　而b ^ (M-2) mod M 就是逆元整数 b`。

 

所以最终要求的 x = n! *[r! *(n-r)!]^(M-2)  (mod M)  

 

#include 
     
      #include 
      
       const int mod = 1000000007;const int maxN = 1e6;long long c[maxN*2 +10];int m,n;void init(){    c[0] = 0;    c[1] = 1;    for(int i =1; i <= maxN*2+5; i++)        c[i+1] = (c[i] *(i+1) ) % mod;}　　int main(){    init();    while(~scanf("%d%d",&n,&m))    {        long long ans = c[n - 1 + m - 1];        ans = (ans * pow(c[n-1],mod - 2)) % mod;        ans = (ans * pow(c[m - 1] ,mod - 2)) % mod;        printf("%lld\n",ans);    }    return 0;}
      
     

 

 题目：

思路：用公式求 等比数列 % 10^9+7

　　　这仍旧是除法取模；

 

sn=(a1(q^n-1))/(q-1) % M =  (a1(q^n-1))*（q-1）^ (M　　-1) % M; 　　

#include 
     
      using namespace std;const int mod = 1e9+7;long long pow(long long n,long long m){    long long ans = 1;    while(m > 0)    {        if(m & 1)ans = (ans * n) % mod;        m = m >> 1;        n = (n * n) % mod;    }    return ans;}int main(){    int n;    cin >>n;    cout<< ((pow(3, n+1)-1)*pow(2, mod-2))%mod<