洛谷 Array 数论
题目:
对于长度为n的数组A,A中只包含从1到n的整数(可重复)。如果A单调不上升或单调不下降,A就可称为美丽的。 找出在长度为n时,有几个美丽的A。
思路:
这是一道数论题。
我们先找找“单调不递减的A”。
1.构造模型:设一个长度为(2*n-1)的序列,用1填满n个空,剩余(n-1)个空;
2.一一对应:找到每一个“1”,用其前方总共的“空格数”构成新序列。如下图所示。

3.合理性:构成的序列满足两个条件。
- (1)不递减:因为空格的数目只会累加。(如果两个“1”相邻的话会出现新序列中有相同数字的情况)
- (2)新序列中每个数字都是0到n-1的整数(可重复)对应题干中“从1到n的整数”:因为空格的数目最多只有n-1。
可见,单调不递减的A的数目=。
易得,单调不递增的A的数目=单调不递减的A的数目=。
所以,由容斥定理得,答案=不递增+不递减-既不递增.也不递减(常数序列) .
代码展示:
#include<stdio.h>
#include<stdlib.h>
const int mod=1000000007;
long long ny(long long x)//逆元 取模
{int cf=mod-2;long long base=x,ans=1;while(cf){if(cf%2==1) ans*=base;ans%=mod;base=base*base;base%=mod;cf>>=1;}return ans;
}
long long c(int x,int y)//计算组合数
{long long fz=1,fm=1,ans;int i;for(i=x;i>=x-y+1;i--) {fz*=i;fz%=mod;}for(i=1;i<=y;i++){fm*=i;fm%=mod;}fm=ny(fm);ans=fz*fm;ans%=mod;return ans;
}
long long zj;
int main()
{//答案是c(2n,n)-n int n,i;scanf("%d",&n);zj=c(2*n,n);zj-=n;if(zj<0) zj+=mod;printf("%lld",zj);return 0;
}
相关文章:
洛谷 Array 数论
题目: 对于长度为n的数组A,A中只包含从1到n的整数(可重复)。如果A单调不上升或单调不下降,A就可称为美丽的。 找出在长度为n时,有几个美丽的A。 思路: 这是一道数论题。 我们先找找“单调不递…...
简明SQL条件查询指南:掌握WHERE实现数据筛选
条件查询是用于从数据库中根据特定条件筛选数据行的一种方式,它避免了检索整个表中的数据。通常,使用 WHERE 子句来定义过滤条件,只有符合这些条件的数据行才会被返回。 SQL中的运算符有:、!、<、> 等,用于进行…...
通过HbaseClient来写Phoenix表实现
由于数据存储在Hbase上,并且上层使用了Phoenix来读写数据。并且由于数据的列字段不固定,并且可能由于Hbase表列和Phoenix的表列字段不一致,使用Phoenix写入的数据会导致写出报错的问题出现。所以这里直接使用HbaseClient写入到Hbase表中&…...
uniapp qiun charts H5使用echarts的eopts配置不生效
原因是:使用web的要设置 echartsH5 :echartsH5"true" <template><view class"charts-box"><view class"chart-title"> 趋势</view><qiun-data-chartstype"column":eopts"eopts":cha…...
嵌入式Linux驱动开发(LCD屏幕专题)(三)
1. 硬件相关的操作 LCD驱动程序的核心就是: 分配fb_info设置fb_info注册fb_info硬件相关的设置 硬件相关的设置又可以分为3部分: 引脚设置时钟设置LCD控制器设置 2. 在设备树里指定LCD参数 framebuffer-mylcd {compatible "100ask,lcd_drv&qu…...
MySQL视图用户管理
文章目录 视图视图的规则用户用户信息创建用户删除用户修改密码 用户权限给用户授权回收权限 视图 视图是一个虚拟表,其内容由查询定义。同真实的表一样,视图包含一系列带有名称的列和行数据。视图的数据变化会影响到基表,基表的数据变化也会…...
我发现了一个很好看的字体,霞鹜文楷!如何换windows和typora字体?
1、字体 官方地址如下,下载也很简单。 https://github.com/lxgw/LxgwWenKai 有1W多的stars。 方式: 直接打包下载。下载不来,可以联系我。 然后ttf的文件,全部安装就行了。 reg save "HKCU\Control Panel" .\res…...
微软8月系统更新引发问题:虚拟内存分页文件出现错误
微软的八月系统更新引发了一系列问题,其中包括“UNSUPPORTED_PROCESSOR”蓝屏错误和文件管理器故障。尽管微软已经修复了前者,但据国外科技媒体Windows Latest报道,仍有用户反馈在非微星设备上出现“fault in nonpaged area”蓝屏错误。 如果…...
swiper删除虚拟slide问题
在存在缓存的情况下,删除较前的slide,会出现当前slide与后一个slide重复出现的情况 假设当前存在5个slide,且这5个slide已缓存,则删除slide2后,仍为5个slide,且slide2的内容变为slide3的内容,此…...
FPGA实战小项目2
基于FPGA的贪吃蛇游戏 基于FPGA的贪吃蛇游戏 基于fpga的数字密码锁ego1 基于fpga的数字密码锁ego1 基于fpga的数字时钟 basys3 基于fpga的数字时钟 basys3...
一些关于完整小程序项目的优秀开源
转载自: 35个项目,开源,开源! (qq.com) 那几本霸占我休息时间的PDF! (qq.com) 13个超强的 SpringBoot 实战项目 (还不赶紧收藏起来) (qq.com) 用SpringBoot开发一个人脸识别系统!…...
Windows模拟器推荐
物是人非事事休,欲语泪先流 Windows模拟器推荐 如果你需要在 Windows 操作系统之外运行 Windows 应用程序或测试不同版本的 Windows,有几个 Windows 模拟器和虚拟机软件可供选择。以下是一些常用的 Windows 模拟器和虚拟机软件: VirtualBox&…...
搭建RabbitMQ消息服务,整合SpringBoot实现收发消息
作者主页:Designer 小郑 作者简介:3年JAVA全栈开发经验,专注JAVA技术、系统定制、远程指导,致力于企业数字化转型,CSDN博客专家,蓝桥云课认证讲师。 目录 一、前言1.1 什么是消息队列1.2 RabbitMQ 是什么1.…...
Web framework-Gin(二)
目录 一、Gin 1、Ajax 2、文件上传 2.1、form表单中文件上传(单个文件) 2.2、form表单中文件上传(多个文件) 2.3、ajax上传单个文件 2.4、ajax上传多个文件 3、模板语法 4、数据绑定 5、路由组 6、中间件 一、Gin 1、Ajax AJAX 即“Asynchronous Javascript And XM…...
【聚类】K-Means聚类
cluster:簇 原理: 这边暂时没有时间具体介绍kmeans聚类的原理。简单来说,就是首先初始化k个簇心;然后计算所有点到簇心的欧式距离,对一个点来说,距离最短就属于那个簇;然后更新不同簇的簇心&a…...
超图聚类论文阅读2:Last-step算法
超图聚类论文阅读2:Last-step算法 《使用超图模块化的社区检测算法》 《Community Detection Algorithm Using Hypergraph Modularity》 COMPLEX NETWORKS 2021, SCI 3区 具体实现源码见HyperNetX库 工作:提出了一种用于超图的社区检测算法。该算法的主要…...
React 防抖与节流用法
在React中,防抖和节流是优化性能和提升用户体验的常用技术。下面是它们的用法: 防抖(Debounce):防抖是指在某个事件触发后,等待一段时间后执行回调函数。如果在等待时间内再次触发该事件,将重新…...
发布 VectorTraits v1.0,它是 C# 下增强SIMD向量运算的类库
发布 VectorTraits v1.0, 它是C#下增强SIMD向量运算的类库 VectorTraits: SIMD Vector type traits methods (SIMD向量类型的特征方法). NuGet: https://www.nuget.org/packages/VectorTraits/1.0.0 源代码: https://github.com/zyl910/VectorTraits 用途 总所周知&#x…...
HCIA自学笔记01-冲突域
共享式网络(用同一根同轴电缆通信)中可能会出现信号冲突现象。 如图是一个10BASE5以太网,每个主机都是用同一根同轴电缆来与其它主机进行通信,因此,这里的同轴电缆又被称为共享介质,相应的网络被称为共享介…...
3D封装技术发展
长期以来,芯片制程微缩技术一直驱动着摩尔定律的延续。从1987年的1um制程到2015年的14nm制程,芯片制程迭代速度一直遵循摩尔定律的规律,即芯片上可以容纳的晶体管数目在大约每经过18个月到24个月便会增加一倍。但2015年以后,芯片制…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...
