YZOJ P3846 [2018省队集训]Yist

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

 

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注