题型:给定两个正整数a与b,求$C_{a}^{b} \quad mod(1e9+7)$
递推式:$$C_{a}^{b}=C_{a-1}^{b-1}+C_{a-1}^{b}$$
解析:
$C_{a}^{b}$的含义就是可以理解成从Acwing网站中a位巨佬中选出b位巨佬的总方案数
a位巨佬中抽出b位巨佬的方案数 可以 分为两类
1.情况①:选$\color{red}{抽风}$巨佬
那么此时已经选出了一位$\color{red}{抽风}$巨佬,剩下只要从a-1位巨佬中选出b-1位巨佬
2.情况②:不选$\color{red}{抽风}$巨佬
那么此时情况显然就是从剩下a-1位巨佬中选出b位巨佬
根据加法计数原理有:$$C_{a}^{b}=C_{a-1}^{b-1}+C_{a-1}^{b}$$
公式求组合数 $\quad O(n^2)$
#include<iostream>
using namespace std;
const int mod = 1e9+7;
long long f[2010][2010];
int main()
{
//预处理
for(int i=0;i<=2000;i++)
{
for(int j=0;j<=i;j++)
{
if(!j) f[i][j]=1;
else f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
}
}
int n;
cin>>n;
while(n--)
{
int a,b;
cin>>a>>b;
printf("%ld\n",f[a][b]);
}
}
我知道了，i=0,j只能等于0,所以不会越界
一语点醒梦中人
@垫底抽风
为啥感觉怎么像dp呀？
==就是DP==
卧槽，这样感觉一下就理解了
哈哈哈
$$C_{a}^{b} = C_{a-1}^{b-1} + C_{a-1}^{b}$$
等式左边表示从 a 个元素中选取 b 个元素，而等式右边表示这一个过程的另一种实现方法：任意选择 a 中的某个备选元素为特殊元素，从 a 中选 b 个元素可以由此特殊元素的被包含与否分成两类情况，即 a 个被选择元素包含了特殊元素和 b 个被选择元素不包含该特殊元素。前者相当于从 a - 1 个元素中选出 b - 1 个元素的组合，即 $C_{a-1}^{b-1}$ ；后者相当于从 a - 1 个元素中选出 b 个元素的组合，即 $C_{a-1}^{b}$。
想问一下 f[i][0] 是前 i 个数选0个的方案数是1
f[0][i] 前 0 个数选 i 个的方案数不应该也是 1 吗 就是一个都不选
为啥加上这个就不对了呢
c[i][j],j<=i,不会出现这种情况。c[i][0]表示从i个物品中一个也不选的可能。c[0][j]没有意义吧，从0个物品中选j个物品可能为0.$$C_1^1 = C_0^1 + C_0^0$$如何处理呢
$j$比$i$小，不可能存在从0个里面取1个的。
C(0, 1)不会被更新到，因为设的全局变量 所以 C(0, 1) = 0，C(0, 0) = 1，所以 C(1, 1) = 0 + 1 = 1
我嘞个抽风巨佬
我还记得当时学排列组合的时候，分步骤用乘，分情况用加，这个地方是分为是否选择这个特殊元素，所以将这两种情况加起来。
O(1+2+3+…+a+n)?
不选抽风巨佬有没有可能会选中另外一位巨佬，这样还是从b-1中选a-1个
卧槽这个解析666666
为什么不管是选中还是不选中都是a-1，不选中的话不应该是a吗
不选中，说明不选抽风，那么可选方案就是剩下的a-1中选
好吧
想问lateX如何打出C(a, b)这个公式？
C_{a}^{b}=C_{a-1}^{b-1}+C_{a-1}^{b},然后左右两边同时加$$就可以
请问一下为什么每一个后面要跟一个%mod呀，这样的话不就跟递推式不一样了吗。题解中的那个%mod是来自取模运算的性质吗？
(a+b)%c=(a%c+b%c)%c
理解了，谢谢大佬
请问一下，为什么取模在函数外边不能AC呢
因为会在你模之前就爆了,要随时模
萌新想问问为什么越界了呀，i=0只执行if里的语句呀，i<=2000没有段错误，我将N换成2000，i<=N就段错误了，急！
假设数组大小是N 合法地址是0~N-1 i == N越界了
这里的数组不会越界嘛，i=0的时候 f[i][j]=f[i-1][j-1]+f[i-1][j];
这不@ 一下抽风巨巨
C[0][0]有必要么？
有必要。因为需要把C[1][1]刷成1
woc，看了你上面那个讲解，一目了然！！！！！！！！！！！！！！！！！1