hdu5698瞬间移动(杨辉三角+快速幂+逆元)

瞬间移动

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2121    Accepted Submission(s): 949

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

hdu5698瞬间移动(杨辉三角+快速幂+逆元)

 
Input
多组测试数据。

两个整数n,m(2≤n,m≤100000)

 
Output
一个整数表示答案
 
Sample Input
4 5
 
Sample Output
10

题意:从左上角开始走,每次只能走到右下任意位置,找规律后发现他是一个斜着的杨辉三角。引用一下别人的

hdu5698瞬间移动(杨辉三角+快速幂+逆元)

题目中的n,m是第n行第m列,所以可以得到组合数c(m+n-4,m-2)这个就是答案,用快速幂加逆元计算结果

 #include <iostream>
using namespace std;
typedef long long ll;
const int mod = 1e9 + ;
ll quick_pow(ll a, ll b) { ///快速幂求逆元
ll ans = ;
while(b) {
if(b % ) {
ans *= a;
ans %= mod;
}
a *= a;
a %= mod;
b /= ;
}
return ans;
}
ll C(int m, int n) { ///组合数公式:C(m, n) =m!/(n!(m-n)!)
if(n > m)
return ;
ll ans = ;
for(int i = ; i <= n; i++) {
ll a, b;
a = (m - n + i) % mod;
b = i % mod;
ans = ans * (a * quick_pow(b, mod - ) % mod) % mod;
}
return ans;
}
int main() {
ll m, n;
while(~scanf("%lld %lld",&n,&m)) {
printf("%lld\n",C(m+n-,m-));
}
return ;
}
上一篇:C#动态操作DataTable(新增行、列、查询行、列等)


下一篇:java进阶(23)--List接口