AcWing 885：求组合数 I ← 杨辉三角
【题目来源】
https://www.acwing.com/problem/content/887/
【题目描述】
给定 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
【算法分析】
● 本题利用公式 C(i, j)=C(i-1, j-1)+C(i-1, j) 进行组合数求解。
● 杨辉三角是二项式系数在三角形中的一种几何排列。
（1）杨辉三角第 n 行包含 n 个数字，对应二项式 (a+b)ⁿ⁻¹ 展开式的系数。
（2）杨辉三角第 n 行第 k 个数等于组合数 C(n-1,k-1)。
（3）杨辉三角第 n 行的数字和为 2ⁿ⁻¹。
（4）杨辉三角左对齐后，沿 45° 斜线（↙方向）的数字和构成斐波那契数列。
（5）杨辉三角左对齐后，第 i 行第 j 列的数=第 i-1 行第 j-1 列的数+第 i-1 行第 j 列的数。正是组合数性质 C(i, j)=C(i-1, j-1)+C(i-1, j) 的几何体现。
【算法代码】
#include<bits/stdc++.h>
using namespace std;int c[2005][2005];
const int mod=1e9+7;int main() {int n;cin>>n;for(int i=0; i<=2000; i++) {for(int j=0; j<=i; j++) {if(j==0) c[i][j]=1;else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}}while(n--) {int x,y;cin>>x>>y;cout<<c[x][y]<<endl;}return 0;
}/*
in:
3
3 1
5 3
2 2out:
3
10
1
*/
【参考文献】
https://www.acwing.com/solution/content/87578/
https://blog.csdn.net/hnjzsyjyj/article/details/147568269
https://www.acwing.com/solution/content/21902/
https://blog.51cto.com/u_15302000/4981839
相关文章：
AcWing 885：求组合数 I ← 杨辉三角
【题目来源】 https://www.acwing.com/problem/content/887/ 【题目描述】 给定 n 组询问，每组询问给定两个整数 a，b，请你输出 C(a,b) mod (10^97) 的值。 【输入格式】 第一行包含整数 n。 接下来 n 行，每行包含一组 a 和 b。 …...
Python3:Jupyterlab 安装和配置
Python3:Jupyterlab 安装和配置 Jupyter源于Ipython Notebook项目，是使用Python（也有R、Julia、Node等其他语言的内核）进行代码演示、数据分析、机器学习、可视化、教学的非常好的工具。 最新的基于web的交互式开发环境，适用于n…...
如何搭建spark yarn模式的集合集群
一、环境准备 在搭建 Spark on YARN 集群之前，需要确保以下环境已经准备就绪： 操作系统：推荐使用 CentOS、Ubuntu 等 Linux 发行版。 Java 环境：确保安装了 JDK 1.8 或更高版本。 Hadoop 集群：已经搭建并运行的 Had…...
智能座舱架构中芯片算力评估
在智能座舱（Intelligent Cockpit）领域，芯片的算力是决定系统性能、响应速度以及用户体验的关键因素之一。 随着汽车智能化程度的不断提高，智能座舱对芯片的算力、功耗、集成度以及安全性提出了更高的要求。 智能座舱架构中芯片算…...
STM32完整内存地址空间分配详解
在STM32这类基于ARM Cortex-M的32位微控制器中，整个4GB的地址空间(从0x00000000到0xFFFFFFFF)有着非常系统化的分配方案，每个区域都有其特定的用途。下面我将详细介绍这些地址区域的分配及其功能： STM32完整内存地址空间分配详解(0x00000000…...
叉车司机N1考试的实操部分有哪些注意事项？
叉车司机 N1 考试实操部分分为场地考试和场内道路考试，以下是一些注意事项： 场地考试 起步：检查车辆仪表和个人仪容，穿好工作服、戴安全帽，不穿拖鞋等不符规定的鞋。同时检查换挡和换向操纵杆在空档位置，…...
【行业特化篇2】金融行业简历特化指南：合规性要求与风险控制能力的艺术化呈现
写在最前 作为一个中古程序猿，我有很多自己想做的事情，比如埋头苦干手搓一个低代码数据库设计平台（目前只针对写java的朋友），比如很喜欢帮身边的朋友看看简历，讲讲面试技巧，毕竟工作这么多年，也做到过高管，有很多面人经历，意见还算有用，大家基本都能拿到想要的offe…...
Linux 定时备份到windows 方案比较
1 传输协议比较 特性SCPRSYNCSFTP基本功能文件传输（本地与远程）文件和目录的同步与传输文件管理（上传、下载、删除等）增量传输不支持增量传输支持增量传输不支持增量传输性能传输速度较慢，效率低高效，适合…...
【网络编程】TCP/IP四层模型、MAC和IP
1. TCP/IP的四层模型 网络模型的目的：规范通信标准，确保不同设备和系统之间能够有效通信 对比OSI模型与TCP/IP模型： OSI模型的七层架构（物理层、数据链路层、网络层、传输层、会话层、表示层、应用层）TCP/IP模型的四…...
Java学习手册： IoC 容器与依赖注入
一、IoC 容器概述 IoC（Inversion of Control，控制反转）容器是 Spring 框架的核心组件之一。它负责创建对象、管理对象的生命周期以及对象之间的依赖关系。通过将对象的创建和管理交给 IoC 容器，开发者可以实现代码的松耦合&#…...
Web 基础与Nginx访问统计
目录 Web基础 域名与DNS 域名的结构 网页与HTML 网页概述 HTML 概述 HTML基本标签 1、HTML 语法规则 2、HTML 文件结构 静态网页和动态网页 HTTP协议概述 HTTP方法 HTTP状态码 Nginx访问状态统计 Web基础 域名与DNS 网络是基于 TCP/IP 协议进行通信和连接的,每一台主机都有一…...
了解Android studio 初学者零基础推荐（1）
线上学习课程链接 开发Andorid App 使用的语言有很多，包括java, kotlin,C,等，首先让我们了解kotlin这个热门语言。 kotlin 程序 fun main() {println("hello,xu") } kotlin中的函数定义语法：函数名称在fun关键字后面࿰…...
Android Studio 2024版，前进返回按钮丢失解决
最近升级完AS最新系统后，顶部的前进和返回按钮默认隐藏了 解决方案： 1. 打开settings 2. 找到左侧 Appearance & Behavior 下面点击 Menus and Toolbars 3. 点击 Main Toolar 4. 点击Left，右键选择 Add Actions 5. 弹框中选择 Main Me…...
详解UnityWebRequest类
什么是UnityWebRequest类 UnityWebRequest 是 Unity 引擎中用于处理网络请求的一个强大类，它可以让你在 Unity 项目里方便地与网络资源进行交互，像发送 HTTP 请求、下载文件等操作都能实现。下面会详细介绍 UnityWebRequest 的相关内容。 UnityWebRequ…...
安装qt4.8.7
QT4.8.7安装详细教程（MinGW 4.8.2和QTCreator4.2.0)_qtcreater482-CSDN博客 QT4.8.7安装详细教程（MinGW 4.8.2和QTCreator4.2.0) 1、下载 1）下载QT4.8.7 http://download.qt.io/archive/ 名称：qt-opensource-windows-x86-mingw482…...
2025系统架构师---管道/过滤器架构风格
引言 在分布式系统与数据密集型应用主导技术演进的今天，管道/过滤器架构风格（Pipes and Filters Architecture Style）凭借其数据流驱动、组件解耦与并行处理能力，成为处理复杂数据转换任务的核心范式。从Unix命令…...
仙宫云ComfyUI —【Wan2.1】AI视频生成部署
【Wan2.1】AI视频生成本地部署与使用技巧全面详解_哔哩哔哩_bilibili 所有模型下载：https://pan.quark.cn/s/9d793aa1b258 Runninghub本期课程工作流下载（可获得1000RH币）：https://www.runninghub.cn/?utm_sourcekol01-RH145 仙…...
学成在线。。。
一：讲师管理 介绍：可以实现对讲师的分页展示，多条件组合分页查询，对讲师的添加，修改，删除操作。 针对于添加来说，使用requestBody注解，搭配postmapping接收数据，使用service层的对象，调用mapper方法，向数据库中保存数据。 修改： 先根据讲师id，查询出讲师，再去…...
Python爬虫实战：获取猫yan电影网最新热门电影数据并做分析，为51观影做参考
一、引言 随着互联网的迅速发展，电影信息获取更加便捷。猫yan电影作为国内知名电影信息平台，提供了丰富电影数据。对于我们而言，获取并分析这些数据，能为用户提供更有价值的观影建议。本文详细介绍使用 Python 的 Scrapy 框架实现猫yan电影数据爬取与分析，为 “五一” 观…...
将有序数组转换为高度平衡二叉搜索树 | 详解与Java实现
文章目录 1. 问题描述2. 方法思路核心思想：分治法 + 递归3. 代码实现Java实现（含注释）4. 复杂度分析5. 关键点解释为何选择中间节点？为何使用 `left + (right - left) / 2` 而非 `(left + right) / 2`？6. 扩展优化迭代法实现（非递归）优化空间7. 总结1. 问题描述 108.将…...
普推知产：商标驳回复审下初步审定公告了！
近日客户的商标驳回复审后终于下初审公告了，经过一年多时间，当时申请时知道这个商标名称会被驳回，因为有相同一模一样的，客户就想要这个名称，因为与创始人的姓名是相关的，普推知产商标老杨经分析后…...
网工笔记-网络层
概述： 两种观点： 1.面向连接的可靠传输 2.面向无连接的，尽最大努力完成交付数据报服务 虚电路服务（可靠传输） 数据报服务（尽力而为） 两者的对比： 不管是虚电路还是数据报服务都是…...
el-Input输入数字自动转千分位进行展示
el-Input输入数字自动转千分位进行展示，存储值不变 子组件： <template><el-input ref"inputRef" :disabled"disabled" clearable v-model"displayValue" v-bind"$attrs" input"handleInput&quo…...
基于 Spring Boot 瑞吉外卖系统开发（九）
基于 Spring Boot 瑞吉外卖系统开发（九） 保存菜品 菜品管理页面提供了一个“新增菜品”按钮，单击该按钮时，会打开新增菜品页面。 请求路径/dish，请求方法POST，参数使用DishDto类接收。 DishDto 添加f…...
C++复习补充 类型转换和RTTI
类型转换和RTTI 类型转换类与类之间的类型转换四种显示类型转换类型转换注意事项RTTI 类型转换 在 C 中，operator int() 是用户定义的类型转换运算符（User-Defined Conversion Operator），允许自定义对象隐式或显式转换为特定类型…...
QT采用mqtt进行通信（17.1）
文章目录 1.试错历程2. qt5.8安装3. 开始搞了4. 测试连接mqtt broker1.试错历程 尝试过网上说的各种版本，官方库和第三方库，试过qt5.9.9, qt5.12, qt5.12.2, qt5.14 等各个版本，都能编译通过，调用mqtt库，但是都不能连接成功，真的是试吐了，不知道他们的为什么都能成功，…...
基于 BERT 微调一个意图识别（Intent Classification）模型
基于 BERT 微调一个意图识别（Intent Classification）模型，你的意图类别包括： 查询天气获取新闻咨询想听音乐想添加备忘查询备忘获取家政服务结束对话增加音量减小音量其他 具体实现步骤（详细版） 1. 准备你…...
人工智能大语言模型与AI芯片新进展：技术演进与商业化路径
人工智能大语言模型与AI芯片新进展：技术演进与商业化路径 Latest Advances in AI Large Language Models and Chips: Technological Evolution and Commercialization Pathways 一、研究背景与意义（Research Background and Significance） 技…...
【Linux】Java 开发者的 Linux 常用命令指南
Java 开发者的 Linux 常用命令指南 目录标题 Java 开发者的 Linux 常用命令指南1. Linux 目录结构2. 系统信息命令3. 服务管理系统服务防火墙管理 4. 文本编辑 (vi/vim)常用模式 5. 文件和目录操作查看与导航创建与删除查看文件内容查找文件 6. 用户管理7. 压缩和解压8. 权限管…...
全开源、私有化部署！轻量级用户行为分析系统-ClkLog
ClkLog是一款支持私有化部署的全开源埋点数据采集与分析系统，兼容Web、App、小程序多端埋点，快速洞察用户访问路径、行为轨迹，并生成多维用户画像。助力中小团队搭建轻量灵活的用户行为分析平台。 为什么需要一款私有化的埋点分析系统&#x…...
【Mybatis】Mybatis基础
文章目录 前言一、搭建MyBatis1.1 创建maven工程1.2 加入log4j日志功能1.3 MyBatis的增删改查1.4 核心配置文件详解 二、MyBatis获取参数值的两种方式2.1 单个字面量类型的参数2.2 多个字面量类型的参数2.3 map集合类型的参数2.4 实体类类型的参数2.5 使用Param标识参数 三、 M…...
（002）Excel 使用图表，统计
第一步新建数据，将数据转成表格： 选中表格数据，右下角小图标：汇总 图表。...
云服务器主动防御策略与自动化防护（下）
三、纵深防御体系构建 1. 系统层防护 # 自动安全更新配置 sudo apt install unattended-upgrades sudo dpkg-reconfigure unattended-upgrades# 内核防护加固 sudo vim /etc/sysctl.conf# 添加以下参数： net.ipv4.conf.all.rp_filter1 net.ipv4.conf.default.rp_f…...
在前端应用领域驱动设计（DDD）：必要性、挑战与实践指南
引言 领域驱动设计（Domain-Driven Design，简称 DDD）起源于后端复杂业务系统建模领域，是 Eric Evans 在 2003 年提出的一套理论体系。近年来，随着前端工程化与业务复杂度的持续提升，"前端也要 DDD&quo…...
【软件工程】需求分析详解
需求分析是确保软件产品符合用户期望、降低返工风险的关键环节。通过系统化的方法，团队可以从多渠道获取需求，利用多种建模技术对需求进行结构化分析，并编写规范的需求规格说明书（SRS），最终通过评审、验证及…...
FPGA-DDS信号发生器
FPGA-DDS信号发生器 DDS基本原理 FPGA实现的DDS（直接数字频率合成）波形生成器是一种高效、灵活的数字信号生成技术，广泛应用于通信、雷达和测试设备中。其核心原理是通过数字计算生成特定频率的波形。 DDS通过相位累加、查找表(LUT)…...
二进制、高位低位、位移操作与进制转换全解
二进制、高位低位、位移操作与进制转换全解 在计算机科学中，理解高位与低位、左移与右移、进制转换与位运算非常重要。这篇文章用清晰直观的方式梳理这些基本概念。 高位与低位 低位：二进制中靠右的位，权值较小（例如 (2^0, 2^1…...
docker存储
注意：数据卷挂载（卷映射）：Docker会自动创建数据卷，并将容器运行所需的文件复制到数据卷中。 目录挂载：如果宿主机上没有对应的目录，容器会因为缺少运行所需的文件而出错。 1.目录挂载 指令&am…...
回归预测 | Matlab实现DBO-LightGBM蜣螂算法优化轻量级梯度提升机多输入单输出回归预测，作者：机器学习之心
回归预测 | Matlab实现DBO-LightGBM蜣螂算法优化轻量级梯度提升机多输入单输出回归预测，作者：机器学习之心 目录 回归预测 | Matlab实现DBO-LightGBM蜣螂算法优化轻量级梯度提升机多输入单输出回归预测，作者：机器学习之心预测效果…...
[ 问题解决 ] sqlite3.ProgrammingError: SQLite objects created in a thread can ...
目录 为什么会出现这个问题？ 解决方法一：每个请求新建自己的连接（推荐） 解决方法二：允许 SQLite 跨线程使用连接（不推荐） 小结 当你在 python 中使用 Flask 里面调用了数据库的操作的时候&a…...
AI智能体开发新范式：多智能体协作与自进化系统的构建之道
一、从单Agent到多Agent：为什么“群体智能”是必然？ 复杂任务的分而治之案例： 电商大促活动的全自动运营商品Agent：实时调价（根据库存/竞品）用户Agent：生成千人千面推荐风控Agent：检…...
js补环境工具使用技巧、补环境实例、重点环境检测点详解
什么是补环境，模拟浏览器环境让浏览器js运行，为什么需要补环境，因为浏览器和本地nodejs环境有差异，网站开发者为了检测用户是否是本地环境运行 主要补的环境Document,Window,Navigator,Location,Element 这是内置原始类型&#…...
TF_LOG 配置及级别详解
以下是Terraform中TF_LOG配置及级别的详解： 配置方法 设置日志级别 通过设置TF_LOG环境变量来启用Terraform的日志功能，并指定日志级别。可以将该变量设置为以下值之一：TRACE、DEBUG、INFO、WARN、ERROR。其中，TRACE级别最为详…...
vue3使其另一台服务器上的x.html，实现x.html调用中的函数，并向其传递数据。
vue3例子 <template><div><iframeload"loadIFreamSite"id"loadIframeSite":src"iframeSrc1"frameborder"0"scrolling"no"allowtransparency"true"style"width: 100%"></iframe&g…...
英语五大基本句型
文章目录 一、主谓二、主谓宾三、主系表什么是什么什么怎么样系动词感官动词 一、主谓 构成：动作的发出者 动作 例句：I run.（我跑步。） 二、主谓宾 构成：动作的发出者 动作 动作的接受者 构成：主语&a…...
什么是 DDoS 攻击？高防 IP 如何有效防护？2025全面解析与方案推荐
一、DDoS 攻击：互联网时代的 “数字核武器” 1. DDoS 攻击的本质与原理 ** 分布式拒绝服务攻击（DDoS）** 通过操控海量僵尸设备，向目标服务器发送洪水般请求，耗尽带宽、连接或计算资源，导致合法用户无法访…...
论文速报《Enhancing Autonomous Driving Systems...：LLM-MPC混合架构增强自动驾驶》
论文链接：https://arxiv.org/pdf/2504.11514 代码链接：https://github.com/ForzaETH/LLMxRobot 0. 简介 自动驾驶领域的传统方法多依赖于数据驱动模型，通过大量标注数据训练实现路径规划和控制。然而，现实世界中道路临时施工、突…...
Nacos 3.0 上线 MCP Registry，支持 MCP 服务注册到发现全流程管理
Nacos 3.0 正式版本发布啦！升级 MCP Registry，围绕着 MCP（Model Context Protocol） 服务管理，MCP 多种类型注册，包含 MCP Server 注册、编排、动态调试和管理，并且提供 Nacos-MCP-Router 可以进…...
一文解析大语言模型量化技术
目录 一、为什么需要量化技术 1、数据规模 2、32位浮点数（FP32） 3、16位浮点数（FP16） 4、Bfloat16（BF16） 5.INT8（8位整数）和INT4（4位整数） 总结&#…...
使用python实现自动化拉取压缩包并处理流程
使用python实现自动化拉取压缩包并处理流程 实现成果展示使用说明 实现成果展示 使用说明 执行./run.sh 脚本中的内容主要功能是： 1、从远程服务器上下拉制定时间更新的数据 2、将数据中的zip拷贝到指定文件夹内 3、解压后删除所有除了lcm之外的文件 4、新建一个ou…...