求组合数算法的实现

(这次因大家强烈要求,补充一点讲解与实质性内容)
_**_这题是求组合数;
算法哟~
理解万岁;

点个赞.
球球啦~QwQ

**_

_题目讲解:给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7) 的值。
_

输入格式
第一行包含整数 n。

接下来 n 行，每行包含一组 a 和 b。

输出格式
共 n 行，每行输出一个询问的解。

数据范围
1≤n≤10000,
1≤b≤a≤2000;

输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1

**_核心代码
这是一个公式

c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod_** __
原理
类似于动态规划(dp)，将情况划分为选第j个和不选第j个
选第j个可以看作从剩下的i-1里再选j-1个 即c[i - 1][j - 1]
不选第j个可以看作从剩下的i-1里再选个 即c[i - 1][j]

#include<bits/stdc++.h>//万能头文件hh

using namespace std;//命名空间

typedef long long LL;//可能越界,所以定义成long long
const int N=2010,mod=1e9+7;定义一个常量
int T,a,b;
int f[N][N];//定义数组;存在二维数组里
void init(int n)//定义一个范围;
{
for(int i=0;i<=n;i++) f[i][0]=1;//判断只要取0个数都为1;
for(int i=0;i<=n;i++)
for(int j=1;j<=i;j++)
f[i][j]=((LL)f[i-1][j-1]+f[i-1][j])%mod;//运用公式
}
int main()//定义主函数;
{
init(N-1);//处理一下,因为N<2010;-1 可以防止它越界;
scanf(“%d”,&T);//输入;
while(T–)
{
scanf(“%d%d”,&a,&b);
printf(“%dn”,f[a][b]);
}
return 0;//收尾hh;
}

先放结论Cba(lucas)≡Cbpap(lucas)Cb mod pa mod p(mod p)
先放结论Cab(lucas)≡Capbp(lucas)Ca mod pb mod p(mod p)

a=akpk+ak−1pk−1+…+a0p0b=bkpk+bk−1pk−1+…+b0p0–①
a=akpk+ak−1pk−1+…+a0p0b=bkpk+bk−1pk−1+…+b0p0–①

(1+x)pk(C1pk∼Cpk−1pkmodp=0)=C0pk×1+C1pk×x+…+Cpkpk×xpk=1+xpk(mod p)−②
(1+x)pk=Cpk0×1+Cpk1×x+…+Cpkpk×xpk(Cpk1∼Cpkpk−1modp=0)=1+xpk(mod p)−②

(1+x)a((1+x)pk=1+xpk(mod p)−式②)(式①)=(1+x)a0((1+x)p)a1((1+x)p2)a2…((1+x)pk)ak=(1+x)a0(1+xp)a1(1+xp2)a2…(1+xpk)ak(mod p)=Cb0a0xb0p0…Cbk−1ak−1xbk−1pk−1Cbkakxbkpk+其他项=Cb0a0…Cbk−1ak−1Cbkakxbkpk+bk−1pk−1+…+b0p0+其他项=Cb0a0…Cbk−1ak−1Cbkakxb+其他项
(1+x)a=(1+x)a0((1+x)p)a1((1+x)p2)a2…((1+x)pk)ak((1+x)pk=1+xpk(mod p)−式②)=(1+x)a0(1+xp)a1(1+xp2)a2…(1+xpk)ak(mod p)=Ca0b0xb0p0…Cak−1bk−1xbk−1pk−1Cakbkxbkpk+其他项=Ca0b0…Cak−1bk−1Cakbkxbkpk+bk−1pk−1+…+b0p0+其他项(式①)=Ca0b0…Cak−1bk−1Cakbkxb+其他项

∴有上式中等式左边(1+x)a(1+x)a和右边累乘的xbxb的系数分别为:
Cba||Cb0a0…Cbk−1ak−1Cbkak(modp)
Cab||Ca0b0…Cak−1bk−1Cakbk(modp)

结合①可知,
a0=a%p,b0=b%pa1=ap%p,b1=bp%p…ak=apk%p,bk=bpk%p
a0=a%p,b0=b%pa1=ap%p,b1=bp%p…ak=apk%p,bk=bpk%p

体现在代码中则只要ap或者bp>pap或者bp>p就继续lucaslucas递归下去直到ap和bp<pap和bp<p,递归的过程相当于自上向下将Cb0a0−>CbkakCa0b0−>Cakbk添加到乘式里，递归终点为ak<p and bk<pak<p and bk<p
#include
#include

using namespace std;

typedef long long LL;

int qmi(int a,int k,int p)
{
int res = 1;
while(k)
{
if(k&1)res = (LL)resa%p;
a = (LL)aa%p;
k>>=1;
}
return res;
}

int C(int a,int b,int p)//自变量类型int
{
if(b>a)return 0;//漏了边界条件
int res = 1;
// a!/(b!(a-b)!) = (a-b+1)…a / b! 分子有b项
for(int i=1,j=a;i<=b;i++,j–)//i<=b而不是<
{
res = (LL)resj%p;
res = (LL)resqmi(i,p-2,p)%p;
}
return res;
}
//对公式敲
int lucas(LL a,LL b,int p)
{
if(a<p && b<p)return C(a,b,p);//lucas递归终点是C_{bk}^{ak}
return (LL)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;//a%p后肯定是<p的,所以可以用C(),但a/p后不一定<p 所以用lucas继续递归
}

int main()
{
int n;
cin >> n;
while(n–)
{
LL a,b;
int p;
cin >> a >> b >> p;
cout << lucas(a,b,p) << endl;
}
return 0;
}

最后

以上就是虚心黑夜为你收集整理的求组合数算法的实现的全部内容，希望文章能够帮你解决求组合数算法的实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。