当前位置: 首页 > news >正文

十二重计数法

Link,限制依次为:

\(1\):球之间互不相同,盒子之间互不相同。

\(2\):球之间互不相同,盒子之间互不相同,每个盒子至多装一个球。

\(3\):球之间互不相同,盒子之间互不相同,每个盒子至少装一个球。

\(4\):球之间互不相同,盒子全部相同。

\(5\):球之间互不相同,盒子全部相同,每个盒子至多装一个球。

\(6\):球之间互不相同,盒子全部相同,每个盒子至少装一个球。

\(7\):球全部相同,盒子之间互不相同。

\(8\):球全部相同,盒子之间互不相同,每个盒子至多装一个球。

\(9\):球全部相同,盒子之间互不相同,每个盒子至少装一个球。

\(10\):球全部相同,盒子全部相同。

\(11\):球全部相同,盒子全部相同,每个盒子至多装一个球。

\(12\):球全部相同,盒子全部相同,每个盒子至少装一个球。


\[5.[n\le m] \]

可否把所有球都扔进去。

\[11.[n\le m] \]

同。

\[1.m^n \]

每个球依次选盒子。

\[8.\binom mn \]

\(n\) 个盒子装球。

\[2.A\binom mn \]

\(n\) 个盒子,塞完球然后排列。

\[9.\binom{n-1}{m-1} \]

插板法。

\[7.\binom{n+m-1}{m-1} \]

插板法,先给每个盒子塞一个球保证正整数。

\[6.\begin{Bmatrix}n\\m\end{Bmatrix} \]

第二类斯特林数定义。

\[4.\sum_{k=1}^m\begin{Bmatrix}n\\k\end{Bmatrix} \]

枚举非空盒子个数。把第二类斯特林数·行贺过来即可。

\[3.\sum_{k=0}^m (-1)^k\binom mk (m-k)^n \]

容斥,枚举 \(k\) 表示至多有 \(k\) 个有球的盒子。


\(p(n,m)\) 表示将 \(n\) 分拆成至多 \(m\) 个正整数的方案数。那么

\[10.p(n,m) \]

\[12.p(n-m,m) \]

\(n-m\) 意为事先给每个盒子扣掉一个球。

\(p(n,m)\) 的方案用点阵表示出来(此处 \(n=7,m=3\)):

\[\begin{bmatrix}1&1&1&1\\1&1\\1\end{bmatrix} \]

其行数 \(\le m\)。将其转置(顺时针转 \(90^\circ\) 然后水平翻转):

\[\begin{bmatrix}1&1&1\\1&1\\1\\1\end{bmatrix} \]

那么其列数 \(\le m\)。这个矩阵还是表示一种拆分方案,且容易知道新矩阵和原矩阵一一对应。

于是 \(p(n,m)\) 变成了:将 \(n\) 分拆成任意多个 \(\le m\) 的正整数的方案数。

这个是付公主的背包。记

\[\operatorname{princess}(n,m)=\prod_{i=1}^m \frac 1{1-x^i} \]

按照原题,可以对每个 \(i\)\(\ln\) 之后一通操作 \(O(m\ln n)\) 得到答案的 \(\ln\) 值,然后 \(\exp\) 回来即可。然后有

\[p(n,m)=[x^n]\operatorname{princess}(n,m) \]

于是

\[10.[x^n]\operatorname{princess}(n,m) \]

\[12.[x^{n-m}]\operatorname{princess}(n,m) \]

http://www.hskmm.com/?act=detail&tid=27943

相关文章:

  • Java高手速成--吃透源码+手写组件+定制开发
  • 【Excel】账单数据分析(数据透视表的简单应用)
  • CSP/NOIP 历年题解导引
  • 记一次Windows 10 无法打开计算器、照片等系统自带小工具问题解决
  • lca(倍增)
  • [SpringCloud][7]负载均衡介绍,以及一些搭建
  • BERT模型简化技术提升效率与容量
  • 251010
  • Redis 64字节分界线与跳表实现原理 - 实践
  • 新手报道
  • VUE---await的运用
  • 供应链业务架构设计概览
  • VS Code保存.vue文件自动格式化标签的问题
  • 基于最小二乘(LS)信道估计的MATLAB实现
  • 让老弟做个数据同步,结果踩了 7 个大坑!
  • 2025焊接件加工制造厂家口碑最新推荐榜:实力工艺与市场口碑
  • 2025机械加工厂家实力排行榜:技术精度与供货效率权威测评
  • 2025 年最新推荐!依托优质运输网络的国际搬家海运公司排行榜:覆盖澳洲多地家具海运需求澳洲/悉尼/墨尔本/大型家具海运公司推荐
  • 完整教程:计算机环境、用户与系统变量
  • 2025耐磨轮胎厂家TOP5推荐:超强抓地力与持久耐用性深度
  • CF做题记录
  • 2025 年中国搬家服务公司最新推荐榜:聚焦海运移民家具运输等需求,精选优质企业实测解析国际/国际海运/国际移民/家具海运/回国搬家海运公司推荐
  • NVIDIA CUDA 镜像 Docker 容器化部署全流程
  • AI时代,程序员的核心竞争力:从“编码工匠”到“元问题架构师”的终极进化
  • 小雅
  • 易基因:JEM(IF10.6):单细胞转录组测序(scRNA-seq)揭示过敏性肺部疾病的调控网络|项目文章
  • Services.AddRazorPages解释
  • 2025 年金属线槽厂家最新推荐排行榜:涵盖不锈钢、铝合金、防火等多类型产品,助您精准挑选优质厂家企业
  • 02_通讯录实现
  • 2025 空气离合器生产厂家最新推荐榜:电网冲击缓解技术测评与可靠性排行,含单片多片机型及核心部件企业