P8315

P8315 Šarenlist 题解 正难则反，显然总方案数 \(k^{n-1}\)，考虑统计不合法方案数。 题目要求：所有特殊路径上都至少有两种不同颜色。不合法的就是：每条特殊路径上的颜色分别相同。 范围极小，可以容斥。记特殊路径集 \(\{P\}\)，枚举其子集 \(\{S\}\)，表示 \(\ ......

P8315 T3 写太慢了，就没看这道/gg。错过简单题+1。 不好直接对边或路径进行考虑，但是发现 \(m\) 非常小，考虑容斥。 即每次钦定集合 \(S\)，强制包含在 \(S\) 内的路径不合法，其它的都可以，容斥系数就是 \(-1^{|S|}\)。每次可以暴力覆盖染色，然后用一个并查集进行维 ......