01序列 卡特兰数

解法:
将01序列置于坐标轴上,起始点为原点。0表示向右走,1表示向上走。这样就可以将前缀0的个数不少于1的个数就可以转换为路径上的点,横坐标大于纵坐标,也就是求合法路径个数。

注意题目mod的数是质数,所以可以使用快速幂求逆元,若不是质数,则需要使用扩展欧几里得算法求逆元。
快速幂:
//01序列 卡特兰数
#include<iostream>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;//因为mod的数是质数可以用快速幂
//如果不是质数就用扩展欧几里得
ll qmi(ll a, ll k, ll p)
{ll res = 1;while (k){if (k & 1) res = res * a % p;a = a * a % p;k >>= 1;}return res;
}
//答案为C2n n /n + 1
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n;ll a = 2 * n, b = n, res = 1;for (ll i = a; i > a - b; --i) res = res * i % mod;for (ll i = 1; i <= b; ++i) res = res * qmi(i, mod - 2, mod) % mod;res = res * qmi(n + 1, mod - 2, mod) % mod;cout << res;return 0;
}
扩展欧几里得:
//01序列 扩展欧几里得
#include<iostream>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;ll exgcd(ll a, ll b, ll& x, ll& y)
{if (!b){x = 1, y = 0;return a;}ll d = exgcd(b, a % b, y, x);y -= a / b * x % mod;return d;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n, x, y; cin >> n;ll a = 2 * n, b = n;ll res = 1;for (ll i = a; i > a - b; --i) res = res * i % mod;for (ll i = 1; i <= b; ++i){exgcd(i, mod, x, y);res = res * x % mod;}exgcd(n + 1, mod, x, y);res = (res * x % mod + mod) % mod;cout << res;return 0;
}
相关文章:
01序列 卡特兰数
解法: 将01序列置于坐标轴上,起始点为原点。0表示向右走,1表示向上走。这样就可以将前缀0的个数不少于1的个数就可以转换为路径上的点,横坐标大于纵坐标,也就是求合法路径个数。 注意题目mod的数是质数,所…...
java实现快速排序
图解 快速排序是一种常见的排序算法,它通过选取一个基准元素,将待排序的数组划分为两个子数组,一个子数组中的元素都小于基准元素,另一个子数组中的元素都大于基准元素。然后递归地对子数组进行排序,直到子数组的长度为…...
【Spring Boot】034-Spring Boot 整合 JUnit
【Spring Boot】034-Spring Boot 整合 JUnit 文章目录 【Spring Boot】034-Spring Boot 整合 JUnit一、单元测试1、什么是单元2、什么是单元测试3、为什么要单元测试 二、JUnit1、概述简介特点 2、JUnit4概述基本用法 3、JUnit5概述组成 4、JUnit5 与 JUnit4 的常用注解对比 三…...
基于安卓android微信小程序的师生答疑交流平app
项目介绍 本课题研究的是基于HBuilder X系统平台的师生答疑交流APP,开发这款师生答疑交流APP主要是为了帮助用户可以不用约束时间与地点进行所需信息。本文详细讲述了师生答疑交流APP的界面设计及使用,主要包括界面的实现、控件的使用、界面的布局和异常…...
开发一个接口,需要考虑什么
开发一个对外接口,一般会考虑以下因素: 用户需求:首先要考虑用户的需求,了解他们希望通过接口实现什么样的功能,以及他们期望接口具备怎样的特性和性能。 可扩展性:接口需要具备良好的可扩展性,…...
【owt】owt-p2p的vs工程构建
owt的p2p代码构建一个静态库 Build started... 1>------ Build started: Project: owtTalkP2P, Configuration: Debug Win32 ------ 1>p2ppeerconnectionchannel.cc 1>g:\webrtc_m98_yjf\src\media\base\codec.h : warning C4819: The file contains a character that…...
uniapp系列
MQTT: 1、报错:TypeError: WebSocket is not a constructor 背景:最近使用MQTT协议传递消息,集成在uniapp上,出现此问题 解决:app端需要用"wx://"(安全协议用"wxs://"&a…...
AWS实战(一)-创建S3 存储桶
1)登录AWS账号,选择服务—>存储—>S3。 2)查看存储桶列表 3)点击"创建存储桶"创建bucket。 4)设置跨域 点击编辑,修改跨域设置即可。...
Java实现简单的俄罗斯方块游戏
一、创建新项目 1.首先新建一个项目,并命名为俄罗斯方块。 2.其次新建一个类,命名为Main,或其他的。 二、运行代码 代码如下: package 俄罗斯方块;import java.awt.BorderLayout; import java.awt.Color; import java.awt.Gr…...
深度学习+opencv+python实现车道线检测 - 自动驾驶 计算机竞赛
文章目录 0 前言1 课题背景2 实现效果3 卷积神经网络3.1卷积层3.2 池化层3.3 激活函数:3.4 全连接层3.5 使用tensorflow中keras模块实现卷积神经网络 4 YOLOV56 数据集处理7 模型训练8 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 &am…...
人工智能 :一种现代的方法 第七章 逻辑智能体
文章目录 前言人工智能 :一种现代的方法 第七章 逻辑智能体7.1 基于知识的智能体7.2 Wumpus世界7.4 命题逻辑7.5 命题逻辑定理证明7.5.1推导和证明7.5.2 归结原理7.5.3 horn子句和限定子句7.5.4 前向链接和后向链接 7.6 有效命题逻辑模型求解7.6.1完备的回溯算法7.6…...
从座舱到行泊一体,亿咖通科技做对了什么?
行泊一体赛道又迎来了一个重磅玩家。 据了解,亿咖通科技旗下基于两颗华山二号A1000芯片打造的亿咖通天穹Pro行泊一体智能驾驶计算平台,目前已经正式在领克08上面实现规模化量产交付。 亿咖通天穹Pro智能驾驶计算平台 值得一提的是,该行泊一…...
BMC Helix解决方案落地亚马逊云科技中国区域,同时上线Marketplace
自主数字企业软件解决方案领域的全球领导者BMC今天宣布,由AI赋能的BMC Helix数字化服务管理平台(ITSM)正式部署于由西云数据运营的亚马逊云科技中国(宁夏)区域,实现SaaS服务和容器化部署双模态,…...
第14章 多线程二 (线程调度)
目录 内容说明 章节内容 1、多线程的调度 2、多线程调度——设置优先级...
Spring Cloud GateWay简介
什么是网关 网关是一种充当转换重任的计算机系统或设备,使用在不同的通信协议、数据格式或语言,甚至网关是一种充当转换重任的计算机系统或设备,使用在不同的通信协议、数据格式或语言,甚至体系结构完全不同的两种系统之间进行数…...
耿明雨出席柬方70周年招待会晚宴
11月9日,庆祝柬埔寨独立和建军70周年欢迎晚宴上,全国政协副主席沈跃跃盛邀出席,此次招待会是由柬埔寨王国驻华大使馆主办,在北京励骏酒店圆满召开,晚宴现场;凯西索达大使致辞、中国外交部部长助理徐飞洪等领…...
退役记 + 秋招总结,占坑
感觉需要写点什么东西来记录一下自己的秋招,以及还有一篇退役记没有写。 思考了一下,感觉发在空间并没有很合适,还是写个博客好了。 最近有点颓,就先买个坑在这里,省的彻底咕掉。 如果今年年底还没写出来的话ÿ…...
网络类型及数据链路层的协议
网络类型 --- 根据数据链路层使用的协议来进行划分的。 MA网络 --- 多点接入网络 BMA --- 广播型多点接入网络---以太网协议 NBMA --- 非广播型多点接入网络 以太网协议 --- 需要使用mac地址对不同的主机设备进行区分和标识 --- 以太网之所以需要使用mac地址进行数据寻址&…...
ROC 曲线:健康背景下的应用和解释
一、介绍 在医疗保健领域,做出明智的决策对于改善患者治疗结果、有效分配资源和设计有效的诊断测试至关重要。受试者工作特征 (ROC) 曲线是一个强大的工具,在评估诊断测试的性能、区分健康个体和患病个体以及优化医疗保健干预方面发挥着至关重要的作用。…...
SpringBoot + Disruptor 实现特快高并发处理,使用Disruptor高速实现队列
1 前言 工作中遇到项目使用Disruptor做消息队列,对!你没看错,不是Kafka也不是rabbitmq。Disruptor有个最大的优点就是快,还有一点它是开源的哦,下面做个简单的记录。 2 Disruptor介绍 Disruptor 是英国外汇交易公司…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
