hdu-5698 瞬间移动(数论+快速幂)

题目链接：

瞬间移动

Problem Description

 

有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过去（如从下图中的红色格子能直接瞬移到蓝色格子），求到第nn行第mm列的格子有几种方案，答案对1000000007取模。

 

Input

 

多组测试数据。

两个整数n,m(2<= n,m<=100000)

Output

 

一个整数表示答案

Sample Input

 

4 5

 

Sample Output

 

10

题意：

思路：

跟那个只能向下和向右走有多少种方案差不多,最后的结果就是一个那个是同一个组合数,用快速幂幂和费马小定理搞;

AC代码：

#include <bits/stdc++.h>

/*

#include <iostream>

#include <queue>

#include <cmath>

#include <map>

#include <cstring>

#include <algorithm>

#include <cstdio>

*/

using namespace std;

#define Riep(n) for(int i=1;i<=n;i++)

#define Riop(n) for(int i=0;i<n;i++)

#define Rjep(n) for(int j=1;j<=n;j++)

#define Rjop(n) for(int j=0;j<n;j++)

#define mst(ss,b) memset(ss,b,sizeof(ss));

typedef long long LL;

const LL mod=1e9+;

const double PI=acos(-1.0);

const int inf=0x3f3f3f3f;

const int N=2e5+;

int n,m;

LL dp[*N];

int Init()

{

    dp[]=;

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

    {

        dp[i]=dp[i-]*(LL)i;

        dp[i]%=mod;

    }

}

LL fastpow(LL x,LL y)

{

    LL ans=,base=x;

    while(y)

    {

        if(y&)

        {

            ans*=base;

            ans%=mod;

        }

        base*=base;

        base%=mod;

        y>>=;

    }

    return ans;

}

int main()

{

        Init();

       while(scanf("%d%d",&n,&m)!=EOF)

       {

           if(n==||m==)cout<<""<<"\n";

           else

           {

           n-=;

           m-=;

           LL x=dp[n],y=dp[m];

           LL ans=dp[n+m]*fastpow(x*y%mod,mod-)%mod;

           cout<<ans<<"\n";

           }

       }

    return ;

}