三项式与组合数(lucas板子）

﹏ヽ暗。殇╰゛Y 2022-04-24 09:20 159阅读 0赞

### 1 、三项式展开 ###

![20190420223740769.png][]

其实可以推广到多项式展开

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzIyMjE3_size_16_color_FFFFFF_t_70][]

### 2、排列组合 ###

%%%大佬博客：[https://blog.csdn.net/qq\_34531807/article/details/79795261][https_blog.csdn.net_qq_34531807_article_details_79795261]

![20190420224313530.png][]

1、当n,m都很小的时候直接用杨辉三角求

C(n,m)=C(n-1,m)+C(n-1,m-1)

2、利用乘法逆元   （初始化完之后如果需要多次计算组合相对来说比Lucas快）

void init(){//fac算阶乘  inv算逆元
    	ll fac[N]={1,1},inv[N]={1,1},f[N]={1,1};
    	for(int i=2;i<=1e5;i++){
    		fac[i]=(fac[i-1]*i)%mod;
    		f[i]=(mod-mod/i)*f[mod%i]%mod;
    		inv[i]=inv[i-1]*f[i]%mod;
    	}
    }
    
    C[n][m]=fac[n]%mod*inv[m]%mod*inv[n-m]%mod;

3、当n和m比较大，mod是素数且比较小的时候（10^5左右），通过Lucas定理计算

题目：[https://ac.nowcoder.com/acm/contest/699/F][https_ac.nowcoder.com_acm_contest_699_F]

三项式展开+lucas+快速幂(板子）

#include<iostream>
    #define ll long long
    #define mod 10007
    using namespace std;
    
    ll qpow(int a,int b,int m)//pow(a,b)%m
    {
    	ll result = 1;
    	ll base = a;
    	while(b>0)
    	{
    		if(b&1==1)
    		result=(result*base)%m;
    		base=(base*base)%m;
    		b>>=1;
    	}
    	return result;
    }
    //计算组合数取模
    ll comp(ll a,ll b,int p)// num C(a,b)%p
    {
    	if(a<b)return 0;
    	if(a==b)return 1;
    	if(b>a-b)b=a-b;
    	ll ans=1,ca=1,cb=1;
    	for(ll i=0;i<b;i++)
    	{
    		ca=(ca*(a-i))%p;
    		cb=(cb*(b-i))%p;
    	}
    	ans=(ca*qpow(cb,p-2,mod))%p;
    	return ans;
    }
    ll lucas(ll n,ll m,ll p)
    {
    	ll ans=1;
    	while(n&&m&&ans)
    	{
    		ans=(ans*comp(n%p,m%p,p))%p;
    		n/=p;
    		m/=p;
    	}
    	return ans;
    
    }
    
    int main(){
    	ll a,b, c, d,e,f,g;
    	cin>>a>>b>>c>>d>>e>>f>>g;
    	ll ans=lucas(e+f,e,mod);
    	//cout<<ans<<endl;
    	ans*=lucas(d,g,mod);
    	//cout<<ans<<endl;
    	ans=(((ans*qpow(a,e,mod))%mod*qpow(b,f,mod))%mod*qpow(c,g,mod))%mod;
    	cout<<ans<<endl;
    	return 0; 
    }

[20190420223740769.png]: /images/20220217/fbed02f1116b4bd693b4606e56b365a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzIyMjE3_size_16_color_FFFFFF_t_70]: /images/20220217/f8279d96b6fe4e36b67bb95cb4475932.png
[https_blog.csdn.net_qq_34531807_article_details_79795261]: https://blog.csdn.net/qq_34531807/article/details/79795261
[20190420224313530.png]: /images/20220217/614a525a99144d9ab5761e86800a24c0.png
[https_ac.nowcoder.com_acm_contest_699_F]: https://ac.nowcoder.com/acm/contest/699/F