除法取模练习（51nod 1119 & 1013 ）

题目：1119 机器人走方格 V2

思路：求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 <cstdio>

#include <string>

const int mod = ;

const int maxN = 1e6;

long long c[maxN* +];

int m,n;

void init(){

    c[] = ;

    c[] = ;

    for(int i =; i <= maxN*+; i++)

        c[i+] = (c[i] *(i+) ) % mod;

}

　　

int main(){

    init();

    while(~scanf("%d%d",&n,&m))

    {

        long long ans = c[n -  + m - ];

        ans = (ans * pow(c[n-],mod - )) % mod;

        ans = (ans * pow(c[m - ] ,mod - )) % mod;

        printf("%lld\n",ans);

    }

    return ;

}

题目：1013 3的幂的和

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

　　　这仍旧是除法取模；

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

#include <iostream>

using namespace std;

const int mod = 1e9+;

long long pow(long long n,long long m)

{

    long long ans = ;

    while(m > )

    {

        if(m & )ans = (ans * n) % mod;

        m = m >> ;

        n = (n * n) % mod;

    }

    return ans;

}

int main()

{

    int n;

    cin >>n;

    cout<< ((pow(, n+)-)*pow(, mod-))%mod<<endl;

    return ;

}