首页 > 编程语言 >AcWing算法基础课笔记——求组合数1

AcWing算法基础课笔记——求组合数1

时间:2024-06-22 21:58:32浏览次数:25  
标签:10 le 输出 int 2000 算法 基础课 mod AcWing

求组合数Ⅰ

10万组数据, 1 ≤ b ≤ a ≤ 2000 1 \le b \le a \le 2000 1≤b≤a≤2000,用递推,时间复杂度 O ( N 2 ) O(N^2) O(N2)

思想:
C a b = C a − 1 b + C a − 1 b − 1 C_a^b = C_{a-1}^{b} + C_{a - 1}^{b - 1} Cab​=Ca−1b​+Ca−1b−1​

题目

题目描述:

给定n组询问,每组询问给定两个整数a,b请你输出C(a,b) mod (10^9+7)的值。

输入格式

第一行包含整数n。接下来n行,每行包含一组a和b。

输出格式

共n行,每行输出一个询问的解。

数据范围

1≤n≤10000,1≤b≤a≤2000

输入样例:

3
3 1
5 3
2 2

输出样例:

3
10
1

代码

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 2010, mod = 1e9 + 7;

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] + c[i - 1][j - 1]) % mod;
		}
	}
} 

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

标签:10,le,输出,int,2000,算法,基础课,mod,AcWing
From: https://blog.csdn.net/Sophia2021XJTU/article/details/139888841

相关文章

  • AcWing 5726. 连续子序列
    5726.连续子序列-AcWing题库01trie的不错的练习题。题目说了求一段连续子序列的异或和,因为异或有结合律,所以我们可以直接预处理一个前缀异或和,即\(a[l,r]=sum[r]\operatorname{xor}sum[l-1]\)。然后求一段异或和就变成了求任意两个\(sum\)的异或和,而这就可以用到0......
  • C++ STL容器操作:6种常用场景算法
    C++STL容器操作:6种常用场景算法    •   引言   •   概述   •   查找与计数   ▪   std::find   ▪   std::find_if   ▪   std::find_if_not   ▪   std::find_end   ▪   std::find_first_of......
  • C语言程序设计-2 程序的灵魂—算法
    【例2.1】求1×2×3×4×5。最原始方法:步骤1:先求1×2,得到结果2。步骤2:将步骤1得到的乘积2乘以3,得到结果6。步骤3:将6再乘以4,得24。步骤4:将24再乘以5,得120。这样的算法虽然正确,但太繁。改进的算法:S1:使t=1S2:使i=2S3:使t×i,乘积仍然......
  • 十大经典排序算法——插入排序与希尔排序(超详解)
    一、插入排序1.基本思想直接插入排序是一种简单的插入排序法,基本思想是:把待排序的记录按其数值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。2.直接插入排序当插入第end+1 个元素时,前面的arr[0],arr[1],... ,arr[end]已经......
  • 【离散数学·算法】(复习)
    一、1.算法的属性:1.输入。2.输出。3.正确性。4.有穷性(有限步数)。5.有效性(有限时间内正确执行每个步骤)。6.泛化性。2.指定算法:可用语言or伪代码来描述二、三类问题1.搜索问题:(1)线性搜索:从头到尾一个一个检查。(2) 二分搜索:(假设排列是按递增顺序的)(找到:返回位置;......
  • 基于BP神经网络的64QAM解调算法matlab性能仿真
    1.算法运行效果图预览  2.算法运行软件版本MATLAB2022A 3.部分核心程序%第一部分:加载并可视化数据%loaddata.matreal1=[-7-7-7-7-7-7-7-7-5-5-5-5-5-5-5-5...-1-1-1-1-1-1-1-1-3-3-3-3-3-3-3-3...+7+7......
  • 【球类识别系统】图像识别Python+卷积神经网络算法+人工智能+深度学习+TensorFlow
    一、介绍球类识别系统,本系统使用Python作为主要编程语言,基于TensorFlow搭建ResNet50卷积神经网络算法模型,通过收集'美式足球','棒球','篮球','台球','保龄球','板球','足球','高尔夫球','曲棍球','冰球','橄榄球',&#......
  • 【球类识别系统】图像识别Python+卷积神经网络算法+人工智能+深度学习+TensorFlow
    一、介绍球类识别系统,本系统使用Python作为主要编程语言,基于TensorFlow搭建ResNet50卷积神经网络算法模型,通过收集‘美式足球’,‘棒球’,‘篮球’,‘台球’,‘保龄球’,‘板球’,‘足球’,‘高尔夫球’,‘曲棍球’,‘冰球’,‘橄榄球’,‘羽毛球’,‘乒乓球......
  • 常微分方程算法之编程示例一(欧拉法)
    目录一、研究问题二、C++代码三、计算结果一、研究问题    前面几节内容介绍了常微分方程有限差分格式的推导。为加强对本专栏知识的理解,从本节开始,我们补充一些具体算例及相应的编程。    欧拉法的原理及推导请参考:常微分方程算法之欧拉法(Euler)_欧拉......
  • 如何用GO语言实现快速排序算法?
    本章教程,介绍一下如何用GO语言实现基础排序算法中的快速排序。快速排序(Quicksort)是一种高效的排序算法,它采用分治法策略,将一个数组分成两个子数组,然后递归地对这两个子数组进行排序。一、程序代码packagemainimport( "fmt" "math/rand" "time")//quickSo......