1 条题解
-
0
题目分析
30 pts
暴力枚举,或者暴力 dp (见 60 pts)
60 pts
原题的模型可以转化成对于一个正整数 n,将其分成 k 个正整数相加之和的方案数。
我们考虑非递减的将 n 分解,这样就不会有重复的情况
那么设 表示将数 i 分解为 j 个数相加且最后一个数为 k 的方案数
那么有 ,时间复杂度
到此即为 暴力 dp 部分。
考虑优化:
很明显 是可以用前缀和统计的,加个辅助数组即可做到 的复杂度,期望得分 60 pts
100 pts
类似第二类 数,我们将方案分成两种:
- 至少包含一个 1 的
- 一个 1 都不包含的
设 表示答案,那么表示 1 的答案即为 ,表示 2 的答案即为 (相当于把每个数加上 1),所以有:
,时间
- 1
信息
- ID
- 91
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者