首页 > 其他 > 详细

整数划分

时间:2020-08-14 02:24:02      阅读:53      评论:0      收藏:0      [点我收藏+]

划分为 k 个正整数

\(f_{i,j}\) 为把 \(i\) 划分为 \(j\) 个数的方案数,得:

\[\large f_{i,j}=f_{i-j,j} + f_{i-1,j-1} \]

整体加 \(1\) 和加上 \(1\)

划分为不重复的 k 个正整数

\(f_{i,j}\) 为把 \(i\) 划分为 \(j\) 个数的方案数,得:

\[\large f_{i,j}=f_{i-j,j} + f_{i-j,j-1} \]

整体加 \(1\) 和整体加 \(1\) 后再加上 \(1\)

划分为不大于 m 的不重复的 k 个正整数

\(f_{i,j}\) 为把 \(i\) 划分为 \(j\) 个数的方案数,得:

\[\large f_{i,j}=f_{i-j,j} + f_{i-j,j-1} - f_{i-(m+1),j-1} \]

整体加 \(1\) 和整体加 \(1\) 后再加上 \(1\)

\(i > m\) 时减去后面一项,因为每个数不重复,所以每次转移最多有一个数大于 \(m\),变为 \(m+1\),需要减去其贡献。

[HEOI2014]平衡

划分为 k 个奇数

\(f_{i,j}\) 为把 \(i\) 划分为 \(j\) 个奇数的方案数,\(g_{i,j}\) 为把 \(i\) 划分为 \(j\) 个偶数的方案数,得:

\[\large \begin{aligned} f_{i,j}&=g_{i-j,j}+f_{i-1,j-1} \ g_{i,j}&=f_{i-j,j} \end{aligned} \]

整数划分

原文:https://www.cnblogs.com/lhm-/p/13499402.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!