组合数学
卢卡斯定理
求组合数:
模板题:P3807 【模板】卢卡斯定理:https://www.luogu.com.cn/problem/P3807
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define DOF 0x7f7f7f7f #define endl ‘\n‘ #define mem(a,b) memset(a,b,sizeof(a)) #define debug(case,x); cout<<case<<" : "<<x<<endl; #define open freopen("ii.txt","r",stdin) #define close freopen("oo.txt","w",stdout) #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<long long, long long> PII; const int maxn = 1e6 + 10; const ll mod=1e9+7; ll j[maxn]; ll n,m,p; ll quick_pow(ll a,ll b ,ll p){ ll ans = 1; while(b){ if(b & 1) ans = (ans * a)%p; a = a * a % p; b>>=1; } return ans; } ll C(ll n,ll m){ if(m > n)return 0; return ((j[n] * quick_pow(j[m],p-2,p))%p * quick_pow(j[n-m],p-2,p)%p); } ll Lucas(ll n,ll m){ if(!m)return 1; return C(n%p,m%p)*Lucas(n/p,m/p)%p; } int main(){ int T; j[0] = 1; cin>>T; while(T--){ cin >> n >> m >> p; for(int i=1;i<=p;i++) j[i] = j[i-1] * i % p; cout<<Lucas(n+m,n)<<endl; } return 0; }
链接:https://ac.nowcoder.com/acm/problem/16596
来源:牛客网
题目描述
给定一个多项式(ax+by)k,请求出多项式展开后xnym项的系数。
输入描述:
共一行,包含5个整数,分别为a,b,k,n,m,每两个整数之间用一个空格隔开。
输出描述:
输出共1行,包含一个整数,表示所求的系数,这个系数可能很大,输出对10007取模后的结果。
思路
\[T_{r+1}=C_{k}^{n}*(ax)^n*(by)^m\]
对公式直接求解
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define DOF 0x7f7f7f7f #define endl ‘\n‘ #define mem(a,b) memset(a,b,sizeof(a)) #define debug(case,x); cout<<case<<" : "<<x<<endl; #define open freopen("ii.txt","r",stdin) #define close freopen("oo.txt","w",stdout) #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<long long, long long> PII; const int maxn = 1e6 + 10; const ll mod=1e9+7; ll j[maxn]; ll n,m,p; ll quick_pow(ll a,ll b ,ll p){ ll ans = 1; while(b){ if(b & 1) ans = (ans * a)%p; a = a * a % p; b>>=1; } return ans; } ll C(ll n,ll m){ if(m > n)return 0; return ((j[n] * quick_pow(j[m],p-2,p))%p * quick_pow(j[n-m],p-2,p)%p); } ll Lucas(ll n,ll m){ if(!m)return 1; return C(n%p,m%p)*Lucas(n/p,m/p)%p; } int main(){ j[0]=1; ll a,b,k,n1,m1;cin>>a>>b>>k>>n1>>m1; n=k,m=n1; p=10007; for(int i=1;i<=p;++i){ j[i]=j[i-1]*i%p; } cout<<(((quick_pow(a,n1,p)%p*(quick_pow(b,m1,p)%p))%p)*(Lucas(n,m)%p))%p<<endl; }
相关推荐
computermaths 2020-04-30
SJCHEN 2020-05-04
computermaths 2020-05-02
kuoying 2020-05-01
seasongirl 2020-04-26
kuoying 2020-04-19
starletkiss 2020-04-17
starletkiss 2020-03-28
computermaths 2020-03-04
seasongirl 2020-02-25
kuoying 2020-02-09
willowwgx 2020-02-01
算法与数学之美 2020-02-01
seasongirl 2020-01-31
seasongirl 2020-01-14
seasongirl 2019-12-05
SJCHEN 2019-11-10