YZOJ P3846 [2018省队集训]Yist

时间限制：1000MS      内存限制：524288KB

难度： $7.0$

• 题目描述

有一个 $n$ 个点 $m$ 条边的无向图，结点从 $1$ 到 $n$ 标号，点 $u$ 的初始权值为 $w_u$。你可以对任意结点 $u$ 进行操作，将你的得分（初始为 $0$）加上 $\sum_\limits{(u,v) \in E}w_v$ ，并将 $w_u$ 除以 $2$ 。

给定一个长度为 $k$ 的结点序列 $s_1,s_2,\cdots,s_k$ （$1 \leq s_i \leq n$），在一轮操作中，你需要依次对 $s_1,s_2,\cdots,s_k$ 进行操作。你想知道，在进行了无限轮操作后，你得分的极限是多少。

显然答案一定可以表示成 $P/Q$ 的形式，你需要输出 $P \times Q^{-1}$ 在模 $998244353$ 意义下的值。特别的，如果得分并不收敛，输出 $-1$ 。

• 输入格式

本题有多组数据，请读入到文件结束。

对于每组数据，第一行三个整数 $n,m,k$ ，含义如题所述。

第二行 $n$ 个整数 $w_1,w_2,\cdots,w_n$，表示结点的初始权值。

第三行 $k$ 个正整数 $s_1,s_2,\cdots,s_k$ 。

接下来 $m$ 行，每行两个整数 $u,v$，描述了一条无向边。

• 输出格式

对于每组数据，输出一行一个整数，表示答案。

• 样例输入

• 样例输出

• 数据规模与约定

对于 $20\%$ 的数据，$n,m \leq 5$，$k \leq 10$；

对于 $40\%$ 的数据，$n,m \leq 1000$，$k \leq 2000$；

对于另外 $20\%$ 的数据，数据为随机生成；

对于 $100\%$ 的数据，$1 \leq n,m \leq 10^5$，$1 \leq k \leq 2 \times 10^5$， $1 \leq s_i \leq n, 0 \leq w_i < 998244353$，保证原图没有重边和自环，数据组数不超过 $3$ 组。

 

 

 

---

 

 

考场上想：这不是简单的极限吗？答案 $\times 2$ 不就好了？$60pts$ 到手了！然后就爆零了，因为 $s_k$ 中有的点是重复的。

考虑每个点在第一轮中对答案的贡献 $sum$，若它在 $s$ 中出现 $cnt$ 次，那么在第二轮中该点对答案的贡献为 $sum \cdot 2^{-cnt}$，第三轮中为 $sum \cdot 2^{-2cnt}$，$\cdots$，第 $n$ 轮中为 $sum \cdot 2^{-(n-1)cnt}$ 。

那么做无限轮后，它对答案的贡献就是： $sum \cdot \sum_\limits{i=0}^{\infty} {2^{-cnt}}^i = sum \cdot \frac{2^{cnt}}{2^{cnt}-1}$ 。

关于收敛性的问题：是否存在一条边 $(u,v)$，其中 $u \in s,v \notin s$ 且 $w_v > 0$ 。存在则不收敛，否则收敛。

现在就剩如何求出这个贡献了。

考虑「将大点度点的复杂度摊给小点度点」。

怎么实现？按照点度分块（抽象意义上的分块）。

把点度不小于 $\sqrt{N}$ 的分成一块，剩下的分成另外一块，还是按照 $s_1, s_2, \cdots, s_k$ 的顺序 一 一 处理。

做到其中的某一个点 $s_i$ 时，把它设为 $x$ ，现在要更新所有与 $x$ 直接相连的点的贡献。

如果 $x$ 在块内的话，那么直接暴力更新所有与 $x$ 相连，同时也在块内的点。那么对于那些与 $x$ 相连，同时在块外的点，如果直接暴力更新的话，很显然复杂度就得不到保证。所以可以有一个类似于 $lazy\_tag$ 的思想，就是说当前不直接更新那些在块外的点。设 $tag(x)$ 表示与 $x$ 相连，并且在块外的点的贡献还需要更新 $tag(x)$ 的增量 次，那么只需令 tag[x]++  即可。

如果 $x$ 在块外的话（点度小于 $\sqrt{N}$），那么就可以直接暴力更新所有与 $x$ 相连的点了。同时，在块外的这个 $x$ 还可能会有来自与它相连，并且在块内的点的“贡献信息”（上述的 $tag$），所以遍历所有与它相连，并且在块内的点，计算其对自己的贡献并且把对于自己的增量清零即可。

值得注意的是，$tag(x)$ 表示 $x$ 对外所有与它直接相连，并且不在块内的点的贡献信息，所以记录增量时不能直接在 $tag$ 上修改，应分别记录所有这些点的增量。

可以发现，上面「与 $xxx$ 相连，并且在块内的点」出现了很多次，所以预处理一下即可。