首页
题库
训练
比赛
作业
讨论
排名
登录
Language
English
한국어
简体中文
正體中文
1 条题解
0
DHEnry
SU
@
2026-11-15 21:49:34
题目分析
C. 网络建设
设
d
p
i
,
j
dp_{i, j}
d
p
i
,
j
为有
i
i
i
个节点,深度小于等于
j
j
j
的网络拓扑结构数量。
一个跨星系通信网络可以看作由一个主控站及左右两个跨星系通信网络组成,因此状态转移方程为 $dp_{i, j} = (\sum\limits_{t = 1}^{i - 1} dp_{t, j - 1} \times dp_{i - t - 1, j - 1}) \% 9901$,最后答案为
(
d
p
n
,
k
−
d
p
n
,
k
−
1
+
9901
)
%
9901
(dp_{n, k} - dp_{n, k - 1} + 9901) \% 9901
(
d
p
n
,
k
−
d
p
n
,
k
−
1
+
9901
)
%9901
。
注意:每一个跨星系通信网络的中继站数量只可能是奇数,所以枚举中继站数量时,只能枚举奇数。
时间复杂度:
O
(
n
2
k
)
O(n^2k)
O
(
n
2
k
)
。
1
网络建设
查看题目
登录后递交
讨论
题解
文件
统计
信息
ID
214
时间
1000ms
内存
512MiB
难度
4
标签
图结构
梦熊联盟
梦熊二十连测
2025
递交数
1
已通过
1
上传者
DHEnry
关闭
登录
使用您的 Hydro 通用账户
使用 FMCRAFT 登录
忘记密码或者用户名?