51 nod 1119ロボットの走方格V 2フェマの小さい定理は組み合わせの数を求めます.

タイトル:
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1119
件名:
M＊Nのチェックは、ロボットが左から右下に行って、右か下に行くしかありません.どれぐらいの歩き方がありますか?方法の数が大きいかもしれませんので、Mod 10^9+7の結果を出力するだけです.Inputの1行目は、2つの数M、N、中間はスペースで仕切られています.(2<=m,n<=100000)Output出力走法の数Mod 10^9+7.
考え方:
行列を簡単に書いてみると、行列を時計回りに45°回転させると楊輝三角になります.そこで、問題は組み合わせの数に転化します.まず元の行列の位置を求めます.楊輝三角の位置は位置転換が簡単です.定理がより速く求められます.Cmnmodに対して. p,イコールn!n!(n−m)!mod pですが、nはできません mod pn!∗(n−m) mod pmod pではなくn!nをかける!∗(n−m)!modで pの下の逆元は、フェマの小定理で素早くべき乗して逆元を求めることができます.

#include 
using namespace std;

typedef long long ll;
const int N = 2000000 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
ll fact[N];
ll mod_pow(ll a, ll b, ll p)
{
    ll res = 1;
    a %= p;
    while(b)
    {
        if(b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}
ll C(ll n, ll m, ll p)
{
    if(m > n) return 0;
    return fact[n] * mod_pow(fact[m]*fact[n-m]%p, p-2, p) % p;
}
ll Lucas(ll n, ll m, ll p)//              ，          
{
    if(m == 0) return 1;
    return C(n%p, m%p, p) * Lucas(n/p, m/p, p) % p;
}
int main()
{
    fact[0] = 1;
    for(int i = 1; i < N; i++) fact[i] = fact[i-1] * i % MOD;
    int n, m;
    scanf("%d%d", &n, &m);
    n += m - 2;
    m -= 1;
    printf("%lld
", Lucas(n, m, MOD));
    return 0;
}

暴力的に求める

#include 
using namespace std;

typedef long long ll;
const int N = 100 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
ll mod_pow(ll a, ll b, ll p)
{
    ll res = 1;
    a %= p;
    while(b)
    {
        if(b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}
ll C(ll n, ll m, ll p)
{
    if(m > n) return 0;
    ll res = 1;
    for(int i = 1; i <= m; i++)
    {
        ll a = (n - i + 1) % p;
        ll b = i % p;
        res = res * (a * mod_pow(b, p-2, p) % p) % p;
    }
    return res;
}
ll Lucas(ll n, ll m, ll p)
{
    if(m == 0) return 1;
    return C(n%p, m%p, p) * Lucas(n/p, m/p, p) % p;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    n += m - 2;
    m -= 1;
    printf("%lld
", Lucas(n, m, MOD));
    return 0;
}