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;
}

 

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/193706.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

YOLOv5独家原创改进:最新原创WIoU_NMS改进点,改进有效可以直接当做自己的原创改进点来写,提升网络模型性能精度

💡该教程为属于《芒果书》📚系列,包含大量的原创首发改进方式, 所有文章都是全网首发原创改进内容🚀 💡本篇文章为YOLOv5独家原创改进:独家首发最新原创WIoU_NMS改进点,改进有效可以直接当做自己的原创改进点来写,提升网络模型性能精度。 💡对自己数据集改进有效…

开发知识点-Vue-Electron

Electron ElectronVue打包.exe桌面程序 ElectronVue打包.exe桌面程序 为了不报错 卸载以前的脚手架 npm uninstall -g vue-cli安装最新版脚手架 cnpm install -g vue/cli创建一个 vue 随便起个名 vue create electron-vue-example (随便起个名字electron-vue-example)进入 创建…

Node.js详解

一、是什么 Node.js 是一个开源与跨平台的 JavaScript 运行时环境 在浏览器外运行 V8 JavaScript 引擎&#xff08;Google Chrome 的内核&#xff09;&#xff0c;利用事件驱动、非阻塞和异步输入输出模型等技术提高性能 可以理解为 Node.js 就是一个服务器端的、非阻塞式I/…

关于Chrome中F12调试Console输入多行

在chrome 浏览器中使用console调试的时&#xff0c;如果想在console中输入多行代码&#xff0c;需要进行换行。 这时我们可以使用 [ Shift Enter ] 。也叫&#xff1a; 软回车。

C 语言实现 UDP

广播 发送广播信息&#xff0c;局域网中的客户端都可以接受该信息 #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <string.h> #include <arpa/inet.h>int main() {// 1.创建一个通信的socketint fd socket(PF_INET, …

S32DS踩坑日记五-bootloader跳转APP时触发DefaultISR

S32DS踩坑日记五-bootloader跳转APP时触发DefaultISR bootloader和APP由另一位同事开发过程中&#xff0c;被导师叫回去写论文了。 由于项目不急&#xff0c;接手后未作任何改动&#xff0c;后面硬件工程师手工焊了几块电路版&#xff0c;需要刷上程序测试电路板。然后就遇到了…

Java 通过POI快速导入带图片的excel并且图片不会丢失

## 通过POI快速导入带图片的excel并且图片不会丢失导入带图片的excel,这里也是研究了很久,在之前的博客中也有说明过,在项目使用过程中,发现很多时候导入响应很慢,而且每次导入图片都会丢失几张,所以又花了点时间研究修改了下,具体如下: 这边在导入时,通过自定义注解…

nginx启动命令

普通启动 切换到nginx安装目录的sbin目录下&#xff0c;执行&#xff1a;./nginx 通过配置文件启动 ./nginx -c /usr/local/nginx/conf/nginx.conf /usr/local/nginx/sbin/nginx -c /usr/local/nginx/conf/nginx.conf 其中-c是指定配置文件,而且配置文件路径必须指定绝对路…

MyBatis-Plus 系列

目录&#xff1a; 一、 Spring Boot 整合 MyBatis Plus 二、MyBatisPlus 多数据源配置 三、MybatisPlus —注解汇总 四、MyBatis Plus—CRUD 接口 五、MyBatis-Plus 条件构造器 六、MyBatis-Plus 代码生成器 MyBatis-Plus (opens new window)&#xff08;简称 MP&#xff09…

Dart 3.2 更新,Flutter Web 的未来越来越明朗

参考原文&#xff1a;https://medium.com/dartlang/dart-3-2-c8de8fe1b91f 本次跟随 Flutter 3.16 发布 的 Dart 3.2 &#xff0c;包含有&#xff1a;私有 final 字段的非空改进、新的 interop 改进、对 DevTools 中的扩展支持、以及对 Web 路线图的更新&#xff0c;包括对 Was…

解决requests库中session.verify参数失效的问题

在使用requests库进行HTTP请求时&#xff0c;如果在环境变量中设置了’REQUESTS_CA_BUNDLE’&#xff0c;并且在session对象中设置了verify参数为False&#xff0c;那么API请求会使用环境变量中的值而不是session对象中的值。这是因为在requests库中&#xff0c;当session对象中…

壹基金爱泽瑞金 安全家园物料配送忙

11月9日到10日&#xff0c;瑞金赋能公益陆续收到壹基金、阿里巴巴公益爱心网友捐赠的社区志愿者救援队队伍物资&#xff0c;马不停蹄地把物资配送到河背街社区、金都社区和沙洲坝镇等项目点&#xff0c;扎实稳妥推进项目有序执行。 在这次物资配送中&#xff0c;志愿者冒雨前行…

DC电源模块对效率有什么要求?

BOSHIDA DC电源模块对效率有什么要求&#xff1f; DC电源模块是现代科技中非常重要的组成部分&#xff0c;它是将交流电转换为直流电的装置&#xff0c;可以提供稳定的电源给各种设备和系统使用。效率是DC电源模块的一个关键性能指标&#xff0c;直接影响着模块的整体性能和效…

ssd202d-logo-cmd_bootlogo分析

cmd_bootlogo.c运行过程 common/autoboot.c:593: disp_logo(0); sprintf(cmd_str, "bootlogo %d 1 0 0 0", logo_id); do_display函数 获取对应结构体,里面有各种参数

Vim 从何而来?

Vim 编辑器的创造者、维护者和终身领导者 Bram Moolenaar 为了纪念这位杰出的荷兰程序员&#xff0c;我们今天来聊一聊 Vim 的历史。 Vim 无处不在。它被很多人使用。同时 Vim 可能是世界上 “最难用的软件之一” &#xff0c;但是又多次被程序员们评价为 最受欢迎的 代码编辑…

vite动态配置svg图标及其他方式集合

文章目录 前言使用vite-plugin-svg-icons动态配置安装插件引入图标下载新建组件svg-icon.vue使用 使用vue组件动态配置总结如有启发&#xff0c;可点赞收藏哟~ 前言 在配置化的情况下&#xff0c;图标配置也显得极为重要的 使用vite-plugin-svg-icons动态配置 参考vite-plugin…

软件系统集成指南

软件产品集成是将各种软件组件、模块和代码组装成最终可执行、可应用的软件产品的过程。这个过程涉及到将工作产品转化为产品的组装过程。在软件工程中&#xff0c;产品集成是一个重要的环节&#xff0c;通过持续性集成&#xff0c;将产品集成的过程常态化、自动化。做好产品集…

2023 年 数维杯(B题)国际大学生数学建模挑战赛 |数学建模完整代码+建模过程全解全析

当大家面临着复杂的数学建模问题时&#xff0c;你是否曾经感到茫然无措&#xff1f;作为2021年美国大学生数学建模比赛的O奖得主&#xff0c;我为大家提供了一套优秀的解题思路&#xff0c;让你轻松应对各种难题。 让我们来看看数维杯&#xff08;B题&#xff09;&#xff01; …

阿里云的99元服务器和腾讯云的88元云服务器选择哪个?怎么选?

近日&#xff0c;阿里云宣布在2023年双十一优惠活动中推出了一系列降价措施&#xff0c;使得同配置的云服务器比腾讯云更具竞争力。这一消息不仅在云计算领域引起了轰动&#xff0c;更为广大互联网用户提供了更为实惠的选择。 阿里云推出99元一年的服务器&#xff0c;续费价格…

[云原生2.] Kurbernetes资源管理 ---- (陈述式资源管理方式)

1. K8s管理资源的方法类别 1.1 陈述式资源管理方式 主要依赖命令行工具kubectl进行管理 可理解为使用一条命令和参数选项来实现资源的管理操作 1.2 声明式资源管理方式 主要依赖统一资源配置清单进行管理 可以理解为使用yaml配置文件的定义来实现资源的管理操作 1.3 GUI式…