P4827 [国家集训队] Crash 的文明世界

    • 168通过
    • 313提交
  • 题目提供者 Imagine
  • 评测方式 云端评测
  • 标签 二项式定理 动态规划,动规,dp 容斥 数论,数学 组合数学 WC/CTSC/集训队 2011 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Crash 小朋友最近迷上了一款游戏——文明5 (Civilization V)。在这个游戏中,玩家可以建立和发展自己的国家,通过外交和别的国家交流,或是通过战争征服别的国家。

    现在 Crash 已经拥有了一个 $n$个城市的国家,这些城市之间通过道路相连。由于建设道路是有花费的,因此 Crash 只修建了 $n-1$条道路连接这些城市,不过可以保证任意两个城市都有路径相通。

    在游戏中,Crash 需要选择一个城市作为他的国家的首都,选择首都需要考虑很多指标,有一个指标是这样的:

    $$S(i) = \sum_{j = 1}^{n}{\rm dist}(i, j) ^ k$$

    其中 $S(i)$表示第 $i$个城市的指标值,${\rm dist}(i, j)$表示第 $i$个城市到第 $j$个城市需要经过的道路条数的最小值,$k$为一个常数且为正整数。

    因此 Crash 交给你一个简单的任务:给出城市之间的道路,对于每个城市,输出这个城市的指标值,由于指标值可能会很大,所以你只需要输出这个数$\rm mod\ 10007$的值。

    输入输出格式

    输入格式:

    输入的第一行包括两个正整数 $n$和 $k$。

    接下来有 $n-1$行,每行两个正整数 $u, v(1≤u, v≤n)$,表示第 $u$个城市和第 $v$个城市之间有道路相连。这些道路保证能符合题目的要求。

    输出格式:

    输出共 $n$行,每行一个正整数,第 $i$行的正整数表示第 $i$个城市的指标值$\rm mod\ 10007$的值。

    输入输出样例

    输入样例#1: 复制
    5 2
    1 2
    1 3
    2 4
    2 5
    
    输出样例#1: 复制
    10
    7
    23
    18
    18
    

    说明

    $20 \%$的数据满足 $n≤ 5000,k≤ 30$。
    $50 \%$的数据满足 $n≤ 50000,k≤30$。
    $100 \%$的数据满足 $n≤ 50000,k≤ 150$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。