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\) 相连，并且在块内的点」出现了很多次，所以预处理一下即可。