51nod 1627 瞬间移动 - dblank

# 51nod 1627 瞬间移动

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

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

单组测试数据。

<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>