信息
- ID
- 107
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
20 分:城市数和数字都很小,道路数量不会很多,可以直接用 DFS 搜索所有路径并计数。
50 分:动态规划。设 fi 表示到达城市 i 的路径数量。转移时枚举所有能直接到达 i 的城市 j,把 fj 累加到 fi 上。初值 f1=1,最终答案为 fn。
100 分:上述转移需要枚举所有前驱,瓶颈在于最后那一段和式。把和式拆开,利用按位统计(Iverson 括号)把「满足某条件的 j 的 fj 之和」改为对每个二进制位 k 分别统计,即对 k=0∼30 逐位累加满足条件的贡献,从而把每次转移的复杂度从 O(n) 降到 O(logV),总复杂度大幅下降。