Astar2016-Round2B 1003(杨辉三角,求大数组合)
发布时间:2021-03-15 17:24:20 所属栏目:大数据 来源:网络整理
导读: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; } (编辑:51站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |