1 条题解

  • 0
    @ 2026-11-15 21:49:34

    题目分析

    C. 网络建设

    • 设 dpi,jdp_{i, j} 为有 ii 个节点,深度小于等于 jj 的网络拓扑结构数量。
    • 一个跨星系通信网络可以看作由一个主控站及左右两个跨星系通信网络组成,因此状态转移方程为 $dp_{i, j} = (\sum\limits_{t = 1}^{i - 1} dp_{t, j - 1} \times dp_{i - t - 1, j - 1}) \% 9901$,最后答案为 (dpn,k−dpn,k−1+9901)%9901(dp_{n, k} - dp_{n, k - 1} + 9901) \% 9901。
    • 注意:每一个跨星系通信网络的中继站数量只可能是奇数,所以枚举中继站数量时,只能枚举奇数。

    时间复杂度:O(n2k)O(n^2k)。

    • 1

    信息

    ID
    214
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者