51nod 1627 瞬间移动 - dblank

51nod 1627 瞬间移动

<div class="HI">
<div class="M_20 F16E Gray30 LH_200">

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

</div>
</div>
<div class="HI">
<div class="M_20 F16E Gray30">
<div class="F18E Black MB_10">Input</div>

单组测试数据。
两个整数n,m(2<=n,m<=100000)

<div class="F18E Black MT_10 MB_10">Output</div>

一个整数表示答案。
<div class="F18E Black MT_10 MB_10">Input示例</div>
4 5
<div class="F18E Black MT_10 MB_10">Output示例</div>
10
</div> </div> <div class="HI"> <div class="LH_120 P_10 BGGrayF4"> <div class="FL">我们可以递推得到 dpi = dpi-1 + dpi; 且i = 1或者j = 1的时候dpi = 0。由于n 和 m非常的大,我们又通过发现规律的到dpi其实是一个组合数,dpi = C(n+m-4, min(n, m)-2),我们可以用lucas定理来得到这个组合数。</div> <div class="FL">
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 60 + 10, Mod = 1000000007;
typedef long long ll;
ll quick_mod(ll a, ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)
            res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll C(ll n, ll m)
{
    if(m>n)
        return 0;
    ll ans = 1;
    for(int i = 1; i<=m; i++)
    {
        ll a = (n + i - m);
        ll b = i;
        ans = ans  (a  quick_mod(b, Mod - 2) % Mod) % Mod;
    }
    return ans;
}
ll lucas(ll n, ll m)
{
    if(m == 0)
        return 1;
    return C(n, m) * lucas(n/Mod, m/Mod) % Mod;
}
int main()
{
    ll n, m;
    cin>>n>>m;
    cout<<lucas(n+m-4, min(n, m)-2)<<endl;
}

 

</div>
</div>
</div>
<div class="HI"></div>

相关文章

发表新评论