优美的组合数

菜狗原来是我自己

于 2021-09-30 20:08:43 发布

阅读量97

点赞数 1

分类专栏：最美算法文章标签：算法

本文链接：https://blog.csdn.net/pythpnhh/article/details/120571875

版权

最美算法专栏收录该内容

2 篇文章

订阅专栏

本文解析了第一类组合数的原理，通过状态转移方程C(mn) = C(m-1n-1) + C(m-1n)，并用C(a, b)的计算为例题，展示了如何使用C++实现初始化状态转移方程求解。适合理解组合数计算及动态规划应用。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

组合数

第一类组合数的解决方案

易知组合数表示的是在n个物品中选择m个不同物品的方案的数

$C\tbinom{m}{n} = C\tbinom{m - 1}{n - 1} + C\tbinom{m - 1}{n}$
我们可以得到这样的类似于状态转移方程的东西

1.思路

我们可以把其中一种物品的结果拿出来，结果就分成两种

①我们选择的物体被选中，即$ C\tbinom{m - 1}{n }$

②我们选择的物体没有被选中$ C\tbinom{m - 1}{n - 1}$

最后的结果就分为这两种

即满足这种条件。

例题

给定 n 组询问，每组询问给定两个整数 a,b，请你输出 $C\tbinom{a}{b}(109+7)$ 的值。

题解

#include<bits/stdc++.h>

using namespace std;

const int N = 2010, mod = 1e9 + 7;
int n, a, b;
int c[N][N];

void init()//初始化状态转移方程
{
	for(int i = 0; i < N; 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;
		}
}

int main(){
	
	init();
	
	scanf("%d",&n);
	while(n--){
		scanf("%d%d",&a, &b);
		
		cout << c[a][b] << endl;
	}
	return 0;
}