hdu5698瞬间移动+杨辉三角+LUCAS

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

Input
多组测试数据。

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

Output
一个整数表示答案

Sample Input

4 5

Sample Output

10

Source
2016”百度之星” - 初赛（Astar Round2B）

简单的推一下前几个数，可以发现是杨辉三角，给出n,m可知结果是杨辉三角的m+n-3行，m+n-3-(n-1)+1=m-1列，而杨辉三角的i行J列结果为C（j-1，i-1），由于数据有点大。。然后用 Lucas。。。。

#include
#include
#include
#include
#define LL long long
using namespace std;
LL n,m,p;LL quick_mod(LL a, LL b)
{LL ans = 1;a %= p;while(b){if(b & 1){ans = ans * a % p;b--;}b >>= 1;a = a * a % p;}return ans;
}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) % p;LL b = i % p;ans = ans * (a * quick_mod(b, p-2) % p) % p;}return ans;
}LL Lucas(LL n, LL m)
{if(m == 0) return 1;return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}int main(){while(scanf("%I64d %I64d",&n,&m)!=EOF){p=1000000007;long long int hang=(n+m-3);long long int lie=hang-(n-1)+1;//cout<long long out=Lucas(hang-1,lie-1);printf("%I64d\n",out);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！