1 条题解

  • 0
    @ 2026-11-15 15:58:00

    题目分析

    20 分:城市数和数字都很小,道路数量不会很多,可以直接用 DFS 搜索所有路径并计数。

    50 分:动态规划。设 fif_i 表示到达城市 ii 的路径数量。转移时枚举所有能直接到达 ii 的城市 jj,把 fjf_j 累加到 fif_i 上。初值 f1=1f_1=1,最终答案为 fnf_n。

    100 分:上述转移需要枚举所有前驱,瓶颈在于最后那一段和式。把和式拆开,利用按位统计(Iverson 括号)把「满足某条件的 jj 的 fjf_j 之和」改为对每个二进制位 kk 分别统计,即对 k=0∼30k=0 \sim 30 逐位累加满足条件的贡献,从而把每次转移的复杂度从 O(n)O(n) 降到 O(log⁡V)O(\log V),总复杂度大幅下降。

    • 1

    信息

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