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

学习笔记:分拆数与 Ferrers 图

分拆数与互异分拆数

要求:给定一个正整数 \(n\),要求将其划分为 \(m\) 个可重 / 不可重的正整数,问本质不同的方案数。(显然 \(m\)\(\sqrt n\) 同阶。)

不妨令划分结果单调不降,则有两种 DP 路径:

  • 法一:令 \(f_{i,j}\) 表示把 \(i\) 分成 \(j\) 个正整数的方案数。

    • 不可重:考虑将这 \(j\) 个数减去 \(1\)。最多一个元素由 \(1\) 变为 \(0\),组数减少 \(1\);其他时候还是 \(j\) 组。故云 \(f_{i,j}=f_{i-j,j-1}+f_{i-j,j}\)
    • 可重:如果存在 \(1\),可以删除之然后转移;否则仍整体减 \(1\) 转移。故曰 \(f_{i,j}=f_{i-1,j-1}+f_{i-j,j}\)

    该转移方法唯一性很显然。注意到第二维只和 \(j,j-1\) 有关;可以交换前后两维顺序然后滚动。

  • 法二:令 \(n=\sum a_i\),建立 \(a\) 的差分数组 \(d\),则有 \(n=\sum\limits_{i=1}^m \sum\limits_{j=1}^i c_j=\sum\limits_{i=1}^m (n-i+1)\times a_i\)。发现 \(a_i\) 每增大 \(1\),答案会增大 \(n-i+1\)。故转化为『第 \(i\) 个物品重量为 \(n-i+1\)』的完全背包。

    • 不可重:要求每个物品至少选一次。
    • 可重:无限制。

    该方法唯一性更显然。

复杂度均为 \(O(nm)\),即 \(O(V\sqrt V)\)

例:Sets of Complementary Sums

link

Ferrers 图

\(k\) 个分拆出来的数用横向柱状图表示并单调不增排列,得到 Ferrers 图。

例: 的 Ferrers 图(图源 OI Wiki)

将图像斜向翻折得到一组共轭解,原图中的 \(k\) 即为共轭解中的元素最值。故亦可限定分拆结果的最值为 \(k\),则结果仍为 \(f_{n,k}\)。同时适用于分拆数与互异分拆数。

顺带提一嘴杨表:把点替换成 \(1\sim n\),并使得一个点同时大于左侧和上方的值。

似乎就不是很有用了。计数题可能会考。

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

相关文章:

  • DDP 与全局平衡二叉树
  • 并查集 D. Shark [Codeforces Round 484(Div. 2)]
  • 实用指南:Spark核心技术解析:从RDD到Dataset的演进与实践
  • 随笔0
  • 加密算法基本原理、特点及采用场景
  • Hackersdaddy ROUGE CTF 2025 完整解题记录
  • AI元人文系列:透明推理者——下一代大模型架构设计
  • 个人随笔
  • 实用指南:1、docker入门简介
  • 调试parlant的大模型配置,最终自己动手写了g4f的模块挂载 - 教程
  • PowerShell注意点
  • 太极 - MKT
  • 题解:P12410 「知りたくなかった、失うのなら」
  • unity面向组合开发二:EC的代码实践
  • 《咳咳,未来编程大师,顶尖程序员的第一条博客》
  • CSP-JF36
  • 超越炒作:使用Agentic AI构建系统架构
  • K个节点的组内逆序调整
  • 【任务】自然语言处理——情感分析 <上>
  • 文件目录
  • 【Azure App Service】Root CA on App Service
  • QOJ #8147. Math Exam 题解
  • 10.03模拟赛t3
  • 国庆梦熊集训做题记录
  • 文件的逻辑结构
  • python 肘部法则,判点聚类分为几类,K-means聚类分析
  • AT_abc315_f [ABC315F] Shortcuts
  • 紫外UV固化太阳光模拟器的原理 - 教程
  • 每日一题
  • P5709 【深基2.习6】Apples Prologue / 苹果和虫子