P4221 [WC2018]州区划分

    • 66通过
    • 600提交
  • 题目提供者 Imagine
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 数论,数学 欧拉回路 状态压缩,状压 WC/CTSC/集训队 2018 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 10000ms-15000ms / 1024MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    滥用本题评测将被封号!

    题目描述

    小 S 现在拥有 $n$ 座城市,第 $i$ 座城市的人口为 $w_i$,城市与城市之间可能有双向道路相连。

    现在小 S 要将这 $n$ 座城市划分成若干个州,每个州由至少一个城市组成,每个城市在恰好一个州内。

    假设小 S 将这些城市划分成了 $k$ 个州,设 $V_i$ 是第 $i$ 个州包含的所有城市组成的集合。定义一条道路是一个州的内部道路,当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同,不经过任何不属于这个州的城市,且经过这个州的所有内部道路都恰好一次的路径(路径长度可以为 $0$),则称这个州是不合法的。

    定义第 $i$ 个州的满意度为:第 $i$ 个州的人口在前 $i$ 个州的人口中所占比例的 $p$ 次幂,即: QQ20180209203148.png 定义一个划分的满意度为所有州的满意度的乘积。

    求所有合法的划分方案的满意度之和。

    答案对 $998244353$ 取模。 两个划分 {$V_1...V_k$} 和 {$C_1...C_s$} 是不同的,当且仅当 $k \neq s$,或存在某个 $1 \leq i \leq k$,使得 $V_i \neq C_i$。

    输入输出格式

    输入格式:

    从文件 ${\tt walk.in}$ 中读入数据。

    输入第一行包含三个整数 $n,m,p$,表示城市个数、城市之间的道路个数以及题目描述中的常数 $p$。

    接下来 $m$ 行,每行两个正整数 $u,v$,描述一条无向的道路,保证无重边无自环。

    输入第 $m+2$ 行有 $n$ 个正整数,第 $i$ 个正整数表示 $w_i$。

    输出格式:

    输出到文件 ${\tt walk.out}$ 中。

    输出一行一个整数表示答案在模 $998244353$ 意义下的取值。

    即设答案化为最简分式后的形式为 $a/b$ ,其中 $a$ 和 $b$ 的互质。输出整数 $x$ 使得 $bx \equiv a$ mod $998244353$ 且 $0 \leq x < 998244353$。可以证明这样的整数 $x$ 是唯一的。

    输入输出样例

    输入样例#1: 复制
    3 2 1
    1 2
    2 3
    1 1 1
    输出样例#1: 复制
    1

    说明

    【样例$2$下载】

    【提示】

    $x^{p-1} \equiv 1$ mod $p$,其中 $p$ 为质数, $x \in [1,p)$。

    【子任务】(注:表中测试点为子任务) QQ20180209204519.png 本题共$20$个测试点,每个子任务对应测试点如下(与表中不符之处已注明):

    子任务$1$对应测试点$1$;

    子任务$2$对应测试点$2$;

    子任务$3$对应测试点$3$;

    子任务$4$对应测试点$4$;

    子任务$5$对应测试点$5$;

    子任务$6$对应测试点$6-10$($n=21,p=0$);

    子任务$7$对应测试点$11-16$($n=21,p=1$);

    子任务$8$对应测试点$17-20$($n=21,p=2$);

    保证对于所有数据有: $0 \leq n \leq 21$, $0 \leq m \leq n*(n-1)/2$ , $0 \leq p \leq 2$, $1 \leq w_i \leq 100$。

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