Astar2016-Round2B 1003(杨辉三角，求大数组合)
发布时间：2021-03-16 08:30:56 所属栏目：大数据 来源：网络整理
导读：FROM： 2016"百度之星" - 初赛（Astar Round2B） http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=702pid=1003 Problem Description 有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过
|
FROM： 2016"百度之星" - 初赛（Astar Round2B） http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=702&pid=1003 Problem Description 有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过去（如从下图中的红色格子能直接瞬移到蓝色格子），求到第nn行第mm列的格子有几种方案，答案对10000000071000000007取模。http://acm.hdu.edu.cn/data/images/C702-1003-1.jpg Input多组测试数据。 两个整数n,m(2leq n,mleq 100000)n,m(2≤n,m≤100000) Output 一个整数表示答案 Sample Input 4 5 Sample Output 10 分析 （i,j）的值是（i,j-1）和（i-1,j）值的和。 先是采用dp的方法，但超时了，代码主体如下 int dp[2][SZ]; //采用2行数组，否则空间会超 for(i=2;i<=m;i++){
dp[0][i]=1;
dp[1][i]=i-1;
}
int k=2;
int f=0;//dp[][0]
while(++k<=n){
for(i=m-1;i<=m;i++)
dp[1-f][i]=(dp[1-f][i-1]+dp[f][i])%mod;
f=1-f;
}
cout<<dp[f][m];后来分析发现，这是杨辉三角，百度查了求杨辉三角某个位置值的方法，第n行的m个数可表示为 C(n-1,m-1) 。注意：这边的行列和题中不同。
因为n，m较大，想了很久，没想到合适的求法，继续百度到了求解方法：http://www.xuebuyuan.com/1154396.html 采用了Lucas定理。赛后发现很多人也是采用了这个方法。 代码 #include <iostream>
using namespace std;
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#define EACH(it,a) for(auto it=begin(a);it!=end(a);it++)
#define LL long long
#define INF 0x3f3f3f3f
const int SZ=100002;
const int mod=1000000007;
const int p=1000000007;
LL Pow(LL a,LL b,LL mod)
{
LL ans=1;
while(b)
{
if(b&1)
{
b--;
ans=(ans*a)%mod;
}
else
{
b/=2;
a=(a*a)%mod;
}
}
return ans;
}
LL C(LL n,LL m)
{
if(n<m)
return 0;
LL ans=1;
for(int i=1;i<=m;i++)
{
ans=ans*(((n-m+i)%p)*Pow(i,p-2,p)%p)%p;
}
return ans;
}
LL Lucas(LL n,LL m)
{
if(m==0)
return 1;
return (Lucas(n/p,m/p)*C(n%p,m%p))%p;
}
int main()
{
ios_base::sync_with_stdio(0);
#ifdef LJY
//freopen("in.txt","r",stdin);
#endif
int i,j;
int n,m;
while(cin>>n>>m){
if(n<m)
swap(n,m);
//C n+m-4,m-2
int a=n+m-4,b=m-2;
if(a-b<b)
b=a-b;
//C a,b
LL ans=Lucas(a,b);
cout<<ans<<endl;
}
return 0;
}
（编辑：衡阳站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
