首页 > 其他 > 详细

cogs2823求组合数(lucas定理

时间:2019-08-19 00:43:44      阅读:72      评论:0      收藏:0      [点我收藏+]

http://cogs.pro:8080/cogs/problem/problem.php?pid=vNQJJVUVj

再写个数学水题,其实lucas适用于m,n比较大而p比较小的情况。

题意:给出两个数n,m,求出C(n,m) mod 1000000007的值 (n <= 2 *1e5)

思路:先预处理出组合数,其中逆元用快速幂求,因为如果p是质数,a^p = a (mod p),a的逆元就是a^(p-2)。然后直接lucas就完了。

技术分享图片
 1 #include<bits/stdc++.h>
 2 #define fo(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout);
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 ll pow_mod(ll a,ll x,ll p){
 7     ll ret = 1;
 8     while(x){
 9         if(x&1) ret = ret*a%p;
10         a = a*a%p;
11         x >>= 1;
12     }
13     return ret;
14 }
15 
16 ll C(ll n,ll m, ll p){
17     if(m==0) return 1;
18     if(m>n-m) m = n-m;
19     ll up = 1,down = 1;
20     for(int i=1;i<=m;i++){
21         up = (up*(n-i+1))%p;
22         down = down*i%p;
23     }
24     return up*pow_mod(down,p-2,p)%p;
25 }
26 
27 ll lucas(ll a,ll b,ll p){
28     if(b==0) return 1;
29     return C(a%p,b%p,p)*lucas(a/p,b/p,p);
30 }
31 
32 int main(){
33     fo("combination");
34     ll n,m,p=1000000007;
35     cin>>n>>m;
36     cout<<lucas(n,m,p)<<endl;
37     return 0;
38 }
View Code

 

cogs2823求组合数(lucas定理

原文:https://www.cnblogs.com/wzgg/p/11374254.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!