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

科技前沿 • 2025-03-07 07:04 • 阅读 27

大家好，我是讯享网，很高兴认识大家。

1 、三项式展开

讯享网

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

2、排列组合

%%%大佬博客：https://blog.csdn.net/_/article/details/

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

三项式展开+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; }

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

1 、三项式展开

2、排列组合

相关推荐