备战蓝桥杯---组合数学基础1

news/2024/2/28 1:17:23

让我们来几道高中的组合题吧:

1.我们一定有n个向下,为\binom{m}{n}

2.我们挑最大的两个,条件是他们奇偶性相同,为2*A10,2;

3.用捆绑法即可。

4.我们用隔板法,为_{9}^{7}\textrm{C}

5.问题等价于23个相同的球放到3个盒子里,每个盒子至少有一个。

下面我们直接看题:

很显然,当无限制条件时,每个a[i]贡献1+2+...+n,因此我们对没有限制的快速幂,有限制的单独计算即可,下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k,mod=1e9+7,x,y,ck;
map<int,int> mp;
struct node{int x,y;
}a[100010];
bool cmp(node a,node b){if(a.x==b.x) return a.y<b.y;else return a.x<b.x;
}
long long quicks(long long a,long long b){long long i=1;while(b){if(b&1) i=(a*i)%mod;b>>=1;a=(a*a)%mod;}return i;
}
signed main(){cin>>n>>m>>k;if(n%2==0) ck=n/2*(n+1)%mod;else ck=n*((n+1)/2)%mod;for(int i=1;i<=k;i++){scanf("%d%d",&a[i].x,&a[i].y);}sort(a+1,a+k+1,cmp);for(int i=1;i<=k;i++){if(a[i+1].x==a[i].x&&a[i+1].y==a[i].y) continue;if(mp.count(a[i].x)==0) mp[a[i].x]=(ck-a[i].y+mod)%mod;else mp[a[i].x]=(mp[a[i].x]-a[i].y+mod)%mod;}int ans=quicks(ck,m-mp.size());map<int,int>::iterator it=mp.begin();for(;it!=mp.end();it++){ans=(ans*(it->second)+mod)%mod;}cout<<ans;
}

接题:

没有障碍时,就是求n个数的排列,而我们现在相当于限制了每一行不能放的元素(互不相同)。

因此,我们可以吧问题等价于1----n个格子,每一个格子不能放与自己下标相同的元素。

这样子就是一个错排问题:

下面给出错排的求解思路:

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,x,a[205];
long long f(long long n){if(a[n]!=-1) return a[n];else return a[n]=(n-1)*(f(n-1)+f(n-2));
}
signed main(){cin>>n;memset(a,-1,sizeof(a));a[1]=0;a[2]=1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&x);}}if(n<=1) cout<<0;else{ cout<<f(n);}
}

下面看看经典的卡特兰数:

(!!!只有第一段翻折)

组合数的除我们用费马小定理求逆元即可。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,mod;
int pow1(int a,int b){int i=1;while(b){if(b&1) i=i*a%mod;b>>=1;a=a*a%mod;}return i;
}
signed main(){cin>>n>>m;mod=20100403;int ret=n+1-m;for(int i=n+1;i<=n+m;i++) ret=ret*i%mod;int ck=n+1;for(int i=1;i<=m;i++) ck=ck*i%mod;ck=pow1(ck,mod-2);cout<<ck*ret%mod;
}


http://www.ppmy.cn/news/1350015.html

相关文章

golang设置

golangci-lint 代码检查工具的集合&#xff0c;聚集了多种 Go 代码检查工具&#xff0c;如 golint 会自动查找项目中的 .golangci.yml 配置文件 会检查代码中潜在常见问题以及代码风格问题 # 文档&#xff1a;https://golangci-lint.run/ # https://github.com/golangci/golang…

[2024]常用的pip指令

[2024]常用的pip指令 HI&#xff0c;这里是肆十二&#xff0c;好久不见&#xff0c;大家&#xff01; 新年好&#xff01; pip是Python的包管理工具&#xff0c;它可以用来安装、升级、卸载Python包。以下是一些常用的pip指令&#xff1a; 安装包&#xff1a; bash复制代码…

【Python】洛谷P4325 [COCI2006-2007#1] Modulo

P4325 [COCI2006-2007#1] Modulo 题面翻译 给出 10 10 10 个整数&#xff0c;问这些整数除以 42 42 42 后得到的余数有多少种。 第一个样例的十个结果是 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 1,2,3,4,5,6,7,8,9,10 1,2,3,4,5,6,7,8,9,10&#xff0c;有 10 10 10 个不…

Vscode SSH使用云服务器访问内网主机

Vscode SSH使用云服务器访问内网主机 云服务器在配置策略中开放使用到的端口号&#xff0c;比如250和251作为使用。 首先在内网主机上使用ssh-copy-id root云服务器公网IP&#xff0c;将内网主机的公钥放到服务器上 这一步必须完成&#xff0c;不然下面的命令无法成功建立隧…

精读《js 模块化发展》

1 引言 如今&#xff0c;Javascript 模块化规范非常方便、自然&#xff0c;但这个新规范仅执行了 2 年&#xff0c;就在 4 年前&#xff0c;js 的模块化还停留在运行时支持&#xff0c;10 年前&#xff0c;通过后端模版定义、注释定义模块依赖。对经历过来的人来说&#xff0c;…

Hadoop:认识MapReduce

MapReduce是一个用于处理大数据集的编程模型和算法框架。其优势在于能够处理大量的数据&#xff0c;通过并行化来加速计算过程。它适用于那些可以分解为多个独立子任务的计算密集型作业&#xff0c;如文本处理、数据分析和大规模数据集的聚合等。然而&#xff0c;MapReduce也有…

从零开始实现消息队列(二)

从零开始实现消息队列 .核心API交换机类型持久化网络通信Connection和Channel 消息应答模块划分 . 核心API 对于Broker来说,要实现以下核心API,通过这些API来实现消息队列的基本功能. 创建队列(queueDeclare)销毁队列(queueDelete)创建交换机(exchangeDeclare)销毁交换机(exc…

QT学习文件操作类 QFile

&#xff08;一&#xff09;QFile QFile 是 Qt 框架中用于文件处理的一个类。它提供了读取和写入文件的功能&#xff0c;支持文本和二进制文件。QFile 继承自 QIODevice &#xff0c;因此它可以像其他 IO 设备一样使用。 &#xff08;1&#xff09;主要功能 1. 文件读写…

学习记录691@spring面试之bean的作用域

Spring为Bean定义了5种作用域&#xff0c;分别为Singleton&#xff08;单例&#xff09;、Prototype&#xff08;原型&#xff09;、Request&#xff08;请求级别&#xff09;、Session&#xff08;会话级别&#xff09;和Global Session&#xff08;全局会话&#xff09;。 S…

mysql、mybatis中SORT

SORT排序 根据数据表sys_series中HOT&#xff08;int类型&#xff09;进行升序排列&#xff1a; 原来的数据库中存储&#xff1a; 排序 # 结果是HOT字段为null的所有数据都排在最前面&#xff0c;不为null的数据按升序排列 SELECT * FROM sys_series ORDER BY HOT;# 结果是H…

项目02《游戏-13-开发》Unity3D

基于 项目02《游戏-12-开发》Unity3D &#xff0c; 任务 &#xff1a;宠物系统 及 人物头像血条 首先在主面板MainPanel预制体中新建一个Panel&#xff0c; 命名为PlayerInfo 新建Image&#xff0c;作为头像 新建Slider&#xff0c;作为血条 对Panel组件添加一个水…

python从入门到精通(二十):python的exe程序打包制作

python的exe程序打包制作 python打包的概念python打包的模块导入模块安装验证基本语法命令参数文件夹模式单文件模式资源嵌入exe更改图标启动画面&#xff08;闪屏&#xff09;禁用异常提示 python打包的概念 将普通的*.py程序文件打包成exe文件。exe文件即可执行文件&#xf…

林浩然与杨凌云的Java世界奇遇记:垃圾回收大冒险

林浩然与杨凌云的Java世界奇遇记&#xff1a;垃圾回收大冒险 The Java Adventure Chronicles of Lin Haoran and Yang Lingyun: Garbage Collection Odyssey 在一个充满0和1代码森林的世界里&#xff0c;住着两位勇敢的程序员侠侣——林浩然和杨凌云。林浩然是个身怀Java绝技的…

[职场] 如何通过运营面试_1 #笔记#媒体#经验分享

如何通过运营面试 盈利是公司的事情&#xff0c;而用户就是你运营的事情。你需要彻底建立一个庞大而有效的用户群&#xff0c;这样才能让你们的公司想盈利就盈利&#xff0c;想战略就战略&#xff0c;想融资就融资。 一般从事运营的人有着强大的自信心&#xff0c;后台数据分析…

Ainx-V0.2-简单的连接封装与业务绑定

&#x1f4d5;作者简介&#xff1a; 过去日记&#xff0c;致力于Java、GoLang,Rust等多种编程语言&#xff0c;热爱技术&#xff0c;喜欢游戏的博主。 &#x1f4d7;本文收录于Ainx系列&#xff0c;大家有兴趣的可以看一看 &#x1f4d8;相关专栏Rust初阶教程、go语言基础系列…

爬爬今天爬小说————爬虫练习

爬不同的的小说&#xff0c;会有略微的改动。 我今天这个是从一章的提前到全部的提前。 在我们电脑里面了&#xff0c;想怎么看就怎么看。 代码代码&#xff1a; import re import requestsheaders {"User-Agent":"Mozilla/5.0 (Windows NT 10.0; Win64; x6…

Java图形化界面编程——弹球游戏 笔记

Java也可用于开发一些动画。所谓动画&#xff0c;就是间隔一定的时间(通常小于0 . 1秒 )重新绘制新的图像&#xff0c;两次绘制的图像之间差异较小&#xff0c;肉眼看起来就成了所谓的动画 。 ​ 为了实现间隔一定的时间就重新调用组件的 repaint()方法&#xff0c;可以借助于…

【每日一题】牛客网——链表分割

&#x1f4da;博客主页&#xff1a;爱敲代码的小杨. ✨专栏&#xff1a;《Java SE语法》 | 《数据结构与算法》 | 《C生万物》 ❤️感谢大家点赞&#x1f44d;&#x1f3fb;收藏⭐评论✍&#x1f3fb;&#xff0c;您的三连就是我持续更新的动力❤️ &#x1f64f;小杨水平有…

设计模式-状态模式 State

状态模式 一、简介概述二、有限状态机1、分支法2、查表法3、状态模式 三、重点回顾 一、简介概述 状态模式并不是很常用&#xff0c;但是在能够用到的场景里&#xff0c;它可以发挥很大的作用。 状态设计模式是一种行为型设计模式&#xff0c;它允许对象在其内部状态发生变化…

【Kubernetes】kubectl top pod 异常?

目录 前言一、表象二、解决方法1、导入镜像包2、编辑yaml文件3、解决问题 三、优化改造1.修改配置文件2.检查api-server服务是否正常3.测试验证 总结 前言 各位老铁大家好&#xff0c;好久不见&#xff0c;卑微涛目前从事kubernetes相关容器工作&#xff0c;感兴趣的小伙伴相互…
最新文章