本文主要是介绍HDU3944 DP?(大组合数取模：lucas定理)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
有一个杨辉三角，现在从顶点到第n行第k列，只能向下或向右下，问最短路径和模p的值。
要点：
如果n>2*m，此时一直往斜左上走到边界，再一直向上，这样最短，权值总和为C（n+1,m）+（n-m)；如果n<=2*m，就先向上到边界，再斜左上到顶点，这样总和为C(n+1,m+1)+m。
这里n和m很大，所以必须要用lucas定理，需要注意的是Lucas定理处理的p的范围大致为10^5数量级。
这个博客写的还比较清楚：点击打开链接
| 18302598 | 2016-09-20 15:33:34 | Accepted | 3944 | 1466MS | 1576K | 886 B | G++ | seasonal |
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;ll exp_mod(int a,int b,int p)
{ll res=1;while(b!=0)//利用二进制求乘方 {if(b&1) res=(res*a)%p;a=(a*a)%p;b>>=1;}return res;
}
ll comb(int a,int b,int p)
{if(a<b) return 0;if(a==b) return 1;if(b>a-b) b=a-b;//组合的性质，n-m和m是相等的ll ans=1,ca=1,cb=1;for(ll i=0;i<b;++i){ca=(ca*(a-i))%p;//这里ca表示n!/(n-m)! cb=(cb*(b-i))%p;}ans= (ca*exp_mod(cb,p-2,p))%p;//这里对m！求逆元即可 return ans;
}
ll lucas(int n,int m,int p)
{ll ans=1;while(n&&m&&p){ans=(ans*comb(n%p,m%p,p))%p;n/=p;m/=p;}return ans;
}int main()
{int n,m,p,kase=1;while(~scanf("%d%d%d",&n,&m,&p)){printf("Case #%d: ",kase++);if(n>2*m)printf("%I64d\n",(lucas(n+1,m,p)+(n-m))%p);elseprintf("%I64d\n",(lucas(n+1,m+1,p)+m)%p); }return 0;
}这篇关于HDU3944 DP?(大组合数取模：lucas定理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
