1 条题解

  • 0
    @ 2026-11-15 14:10:19

    题目分析

    30 pts

    暴力枚举,或者暴力 dp (见 60 pts)

    60 pts

    原题的模型可以转化成对于一个正整数 n,将其分成 k 个正整数相加之和的方案数。

    我们考虑非递减的将 n 分解,这样就不会有重复的情况

    那么设 f[i][j][k]f[i][j][k] 表示将数 i 分解为 j 个数相加且最后一个数为 k 的方案数

    那么有 f[i][j][k]=∑p=1kf[i−k][j−1][p]f[i][j][k] = \sum_{p = 1}^k f[i - k][j - 1][p],时间复杂度 O(n3k)O(n^3k)

    到此即为 暴力 dp 部分。

    考虑优化:

    很明显 ∑p=1kf[i−k][j−1][p]\sum_{p = 1}^k f[i - k][j - 1][p] 是可以用前缀和统计的,加个辅助数组即可做到 O(n2k)O(n^2k) 的复杂度,期望得分 60 pts

    100 pts

    类似第二类 stirlingstirling 数,我们将方案分成两种:

    1. 至少包含一个 1 的
    2. 一个 1 都不包含的

    设 f[n][k]f[n][k] 表示答案,那么表示 1 的答案即为 f[n−1][k−1]f[n - 1][k - 1],表示 2 的答案即为 f[n−k][k]f[n - k][k] (相当于把每个数加上 1),所以有:

    f[n][k]=f[n−1][k−1]+f[n−k][k]f[n][k] = f[n - 1][k - 1] + f[n - k][k],时间 O(nk)O(nk)

    • 1

    信息

    ID
    91
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者