容斥原理公式c语言,【笔记】组合数学 - osc_3md1xrlp的个人空间 - OSCHINA - 中文开源技术交流社区...

本文主要是介绍容斥原理公式c语言,【笔记】组合数学 - osc_3md1xrlp的个人空间 - OSCHINA - 中文开源技术交流社区...,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

开新坑辣。。。。。

排列组合

排列:P(n,r) = n! / (n-r)! 组合:C(n,r) = n! / r!(n-r)! 圆排列:P(n,r) / r 多重集排列:

令S是一个多重集,它有k个不同类型的元素,每一个元素都有无穷重复个数。那么S的r-排列的个数为k^r。

令S是一个多重集,它有k个不同类型的元素,各元素重数为n1,n2,...,nk。设S的大小为n = n1 + n2 + ... + nk。则排列数等于n! / (n1!n2!...nk!)

抽屉原理(鸽巢原理)

wiki百科介绍 理解起来还是比较容易的,拓展有拉姆齐定理(虽然是图论上的内容)

特殊序列

掌握它们的应用和推导方式

Catalan序列

wiki百科介绍

f420ef8257447467cc9f8bd6cea23b91.png

214fbe1794f42d6d806ab1d3a3d7ccaf.png

23a78a28770f949c7a303cb2a4e68e4a.png

c44b5d47e55125ac168f965b4cf92e43.png 前20项为(OEIS中的数列A000108):1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190

Stiring数

wiki百科介绍 第一类:将p个有区别的球排成k个非空的圆排列的方案数

4e22bb3ae5c94e337878adf22209fa0c.png

5260ad786591afaf0f8bfcffcabd28d6.png

4be7dead2dd2791810b3b13192d875c0.png 第二类:将p个有区别的球放到k个相同盒子中,奥球没有空盒的方案数

af0914c09d92f4c3b33369689ae048cc.png

4b911982b08b39d0942faf45a53ab062.png 两者关系:

0a7dbfe147b60a47e9ed652ea0888e08.png

容斥原理

60835765823fe76e74b7048872a5e617.png

错位排列

公式法:

c2fdb7dc5b30aefd13b9d0a618e9db25.png 递推法: 考察n≥3时的错位排列,把数字n单独拿出来看,先把n放在第n位。设P是{1,2,...,n-1}的一个排列

如果P是一个错位排列,把其中任意一个数与n交换仍然是一个错位排列,这样的情形可以得到(n-1)D_n-1个{1,2,...,n}的错位排列

如果P不是错位排列,并且只存在一个位置不符合要求(P_x = x)将x和n交换后又是一个错位排列。这里可以得到(n-1)D_n-2个{1,2,...,n}的错位排列。

其他情形都不能得到错位排列

D_n = (n-1)(D_n-1 + D_n-2) (D1 = 0, D2 = 1)

Mobius反演

NULL

棋盘多项式

母函数(生成函数)

普通型生成函数讲解 在学习FFT的时候,已经知道可以用卷积来计算生成函数计数问题,它可以针对一般的多项式计算乘积,而在整数拆分这个问题里,有n个表达式,需要做n次卷积,复杂度O(n²logn),但FFT常数是很大的,观察得知每个多项式是很有规律的,它的第i个多项式中系数为1的项都间隔了i-1个系数为0项,所以我们可以用一个每次变化i-1的k循环来遍历得到每层卷积后的多项式 指数型生成函数讲解

Polya计数定理

置换群

首先给你一个序列,假如: s = {1 2 3 4 5 6} 然后给你一个变换规则 t = {6 3 4 2 1 5} 就是每一次按照t规则变换下去 第一次:6 3 4 2 1 5 第二次:5 4 2 3 6 1 第三次:1 2 3 4 5 6 发现经过几次会变换回去,再变换下去就是循环的了,这就是一个置换群 我们可以这样表示一个置换群,比如按照上面变化规则 1->6->5->1 这些是一个轮换 2->3->4->2 这些是一个轮换 所以可以写为 t = { {1 6 5},{ 2 3 4 } }

如果一个状态经过置换f后跟原来相同, 即S[1]=S[a1],S[2]=S[a2],…,S[n]=S[an] 则称该状态为f 的不动点。

题目中常常出现“本质不同的方案数”,一般是指等价类的数目,题目定义一个等价关系,满足等价关系的元素属于同一等价类。等价关系通常是一个置换集合F,如果一个置换能把其中一个方案映射到另一个方案,则二者是等价的。 那么,置换构成的群就是置换群,就是交换排列顺序而已

二面体群

wiki百科介绍 翻转本质上也是一种置换规则

557d1d72a7cbba8d3c9a5887fcb5f153.png

Burnside引理

设G是集合X上的一个置换群(可以理解为合理的所有的置换方案的集合),S(g)为C中的不动点的着色集合,则可以证明等价类数目为所有S(g)的平均值。

一正方形分成4格,2着色,有多少种方案?其中,经过转动相同的图象算同一方案 对于每种格子我们都有两种选择,所以会有一下16种方案

adf96bf893b4b23092a326431bb94709.png

不动:所有的情况都是不动点 16

旋转90° (1)(2)是不动点 2

旋转180° (1)(2)(11)(12)是不动点 4

旋转270° (1)(2)是不动点 2 (16+2+4+2)/4=6种

Polya计数定理

先把所有方案重复计算相同的次数,再把结果除以重复的次数 设G是集合x上的一个置换群,X中每个元素可以被染成k种颜色,则不等价的着色数为:P=(1 / |G|) *∑K^(nc(g)),nc(g) 为置换中循环节的个数

这篇关于容斥原理公式c语言,【笔记】组合数学 - osc_3md1xrlp的个人空间 - OSCHINA - 中文开源技术交流社区...的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/256901

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

阿里开源语音识别SenseVoiceWindows环境部署

SenseVoice介绍 SenseVoice 专注于高精度多语言语音识别、情感辨识和音频事件检测多语言识别: 采用超过 40 万小时数据训练,支持超过 50 种语言,识别效果上优于 Whisper 模型。富文本识别:具备优秀的情感识别,能够在测试数据上达到和超过目前最佳情感识别模型的效果。支持声音事件检测能力,支持音乐、掌声、笑声、哭声、咳嗽、喷嚏等多种常见人机交互事件进行检测。高效推

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

uva 11044 Searching for Nessy(小学数学)

题意是给出一个n*m的格子,求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码: #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col