AcWing 885. 求组合数 I
原题链接
简单
作者:
kRYST4L
,
2023-05-26 22:37:48
,
所有人可见
,
阅读 25
求组合数 I(数据量a<=2000,b<=2000,递推的方法)
- 性质1:$C_{a}^{0}=1$
- 性质2:$C_{a}^{b}= C_{a-1}^{b-1}+C_{a-1}^{b}$
性质2的证明(有点像01背包)
- $C_{a}^{b}$表示为在a个数里挑b个数的方案数
- 那么从第i个数去考虑,分为两种情况选第i个数和不选第i个数
- 情况1选第i个数:那么剩下b-1个数就在a-1个数里面选,即$C_{a-1}^{b-1}$
- 情况2不选第i个数:那么剩下b个数就在a-1个数里面选,即$C_{a-1}^{b}$
- 情况1和情况2的方案数相加即为$C_{a}^{b}$的方案数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010,mod=1e9+7;
int c[N][N];
int n;
void init()//预处理所有的组合数,时间复杂度在4*10^6
{
for(int i=0;i<N;i++)//坑点:不能写成i<=N,不然会数组越界
for(int j=0;j<=i;j++)
{
if(!j) c[i][j]=1;//这就是定义c[i][0]=1;
else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;//有点像01背包思想
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
init();
while (n -- )
{
int a,b;
cin>>a>>b;
cout<<c[a][b]%mod<<endl;
}
}