组合数是数学的重要概率。
从a个物品中选出b个物品的所有方案数记为。
由于在编程中b，a的数据范围不同我们可以采取不同的方法解决问题。
数据范围较小时，可以直接用递推解决。
递推式：
为什么会有这个递推式呢，可以用动态规划考虑最后一步，从a个物品中选b个物品，对于最后一个物品b，假设我们选，则需要从前a-1个选b-1个，不选则应该从前a-1个选b个。
代码：
#include
using namespace std;
const int mod=1e9+7;
typedef long long ll;
ll c[2005][2005];
void init(){
for(int i=0;i<=2000;i++){
for(int j=0;j<=i;j++)
{
if(!j)c[i][j]=1;
else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}
return;
}
int main(){
int n;
cin>>n;
while(n--){
int a,b;
cin>>a>>b;
cout< 当数据范围扩大又该怎么做呢
此时有一万组询问，a，b范围位1e5。
此时我们应该用更快的方法。
由，我们可以预处理出阶乘，然后用o(1)的时间复杂度解决询问。
由于需要对除数取模，因此求出逆元代替除数。
#include
using namespace std;
const int N=1e5+10,mod=1e9+7;
typedef long long ll;
ll fact[N],infact[N];
ll qmi(ll a,ll b,ll p){
ll res=1;
while(b){
if(b&1)res=res*a%p;
b>>=1;
a=a*a%p;
}
return res;
}
int main() {
fact[0]=infact[0]=1;
for(int i=1;i>n;
while(n--){
int a,b;
cin>>a>>b;
cout< lucas定理：
若p是质数，则对于任意整数1<=m<=n，
即把a,b看成p进制数，对每一位求组合数再相乘得到ans。
#include
using namespace std;
const int N=1e5+10,mod=1e9+7;
typedef long long ll;
int p;
ll qmi(ll a,ll k){
ll res=1;
while(k){
if(k&1)res=res*a%p;
a>>=1;
a=a*a%p;
}
return res;
}
ll C(ll a,ll b){
ll res=1;
for(int i=1,j=a;i<=b;j--,i++){
res=res*j%p;
res*res*qmi(i,p-2)%p;
}
return res;
}
ll lucas(ll a,ll b){
if(a>n;
while(n--){
ll a,b;
cin>>a>>b;
cout< 当运算过程不取模时结果会很大此时要用到高精度
我们可以将阶乘分解质因数，再将质因数相乘得到答案。
#include
#include
#include
using namespace std;
const int N = 5010;
int primes[N], cnt;
int sum[N];
bool st[N];
void get_primes(int n) //线性筛
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int get(int n, int p) //求阶乘的质因数p的个数
{
int res = 0;
while (n)
{
res += n / p;
n /= p;
}
return res;
}
vector mul(vector a, int b) //高精乘
{
vector c;
int t = 0;
for (int i = 0; i < a.size(); i ++ )
{
t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while (t)
{
c.push_back(t % 10);
t /= 10;
}
return c;
}
int main()
{
int a, b;
cin >> a >> b;
get_primes(a);
for (int i = 0; i < cnt; i ++ )
{
int p = primes[i];
sum[i] = get(a, p) - get(a - b, p) - get(b, p);
}
vector res;
res.push_back(1);
for (int i = 0; i < cnt; i ++ )
for (int j = 0; j < sum[i]; j ++ ) //sum[i]个p
res = mul(res, primes[i]);
for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
return 0;
} 卡特兰数问题引入：
问题 ：n个0和n个1，它们将按照某种顺序排成长度为2n的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个。
建立笛卡尔坐标系，设0代表右走一步，1代表向上走。
原来的问题对应不能走过红线。
用总的方案减去不合法方案为所求。
终点为(n,n),总方案为。
不合法方案必然经过y=x+1,取第一个经过y=x+1的点，令后面的线段对y=x+1做轴对称，终点为（n+1,n-1).任意一条从（0,0）到（n+1,n-1)的路径都对应一条不合法方案。
即。
因此答案为，化简得 。
#include
using namespace std;
typedef long long ll;
const int N = 200010, mod = 1e9 + 7;
int n;
int fact[N], infact[N];
int ksm(int a, int k) {
int res = 1;
while (k) {
if (k & 1) res = (ll)res * a % mod;
a = (ll)a * a % mod;
k >>= 1;
}
return res;
}
void init() {
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i++) {
fact[i] = (ll)fact[i - 1] * i % mod;
infact[i] = (ll)infact[i - 1] * ksm(i, mod - 2) % mod;
}
}
int main() {
init();
cin >> n;
int res = (ll)fact[2 * n] * infact[n] % mod * infact[n] % mod * ksm(n + 1, mod - 2) % mod;
cout << res << endl;
return 0;
} 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）