整数划分问题

2015.01.08 15:23 Thu| 4 visits oi_2015| 2015_算法笔记| Text

整数划分问题

给出正整数 N,询问如下几个问题:

  1. 将 N 划分成若干正整数之和的划分数。
  2. 将 N 划分成 K 个正整数之和的划分数。
  3. 将 N 划分成最大数不超过 K 的划分数。
  4. 将 N 划分成若干奇正整数之和的划分数。
  5. 将 N 划分成若干不同整数之和的划分数。

核心

将 N 划分为 M 个数的方案由两种情况组成:

  • 划分后存在一个正整数的值为 1。
  • 划分后不存在一个正整数的值为 1。

对于第二种情况,可以将其每一项都减去 1 后,等价于 将 N-M 划分为 M 个数的方案。于是得到将 N 划分为 M 个数的方案 $F_{N,M} = F_{N-1, M-1} + F_{N-M, M}$ 。

上述问题的答案

有了这一公式,前两个问题的答案便显然:

显然,将 N 划分成最大数不超过 K 的划分数与将 N 划分成不超过 N 个正整数的划分数相同,于是

将 N 划分成 M 个奇整数的相当于将 ${N+M\over 2}$ 划分为 M 个正整数(当然,N + M 需要为偶数),因此

第五个问题貌似有一些麻烦,其实是一个简单的01背包问题 23333

当然,也可以表示成下面的形式。

QY大神在课件里面还放了两道练习题:战场的数目 和【HEOI2014】平衡。