题意

题目链接
给出一个顶点带权无向图。
定义访问操作：访问一个点，就要把与这个点相邻的点的权值全部都加到答案里去，然后给这个顶点的权值/2。现在给出一个无穷的访问序列中的一个循环节，求最终答案的极限是多少。
注意：本题是在模意义下。

题解

数据范围 ≤ 100000
我们定义一个sumsum数组，其中sum[v]sum[v]表示与vv顶点相邻的所有顶点的权值和。
这样我们扫描一个循环节，只需要把当前顶点v的sum[v]sum[v]加入到答案里面去就好了，然后我们要给顶点vv的权值减半，并且还要更新顶点vv相邻的所有点的sumsum。
这个思路看起来没有问题，但是问题来了，更新顶点v相邻的所有点的sumsum值的时候，如果每个点相邻的点都有99999个这么多。而循环节长度又有100000个这么长，时间复杂度显然就会爆炸了。

我们现在需要一个O(nn‾√)O(nn)的算法。

我们把顶点进行分类，按照这个顶点的度数进行分。
当degv>300degv>300的点，我们把它看作是big点，如果某个点u与big点点相临，那么这个u点的sum[u]sum[u]中不应该包含big点的权值，这样的话，big点就不需要更新周围点的sum值了。

当degv≤300degv≤300的点，我们把它看作是small点，如果某个点u与small点相邻，那么这个u点的sum[u]sum[u]中应该包含small点的权值，并且访问small点时候，也应该从small点出发更新相邻点的sumsum值。

这样的话，更新操作的时间复杂度就变成了O(k∗300)O(k∗300)
我们继续来看询问操作，每次到一个点的时候，把这个点的sum[u]sum[u]加到答案里去，并且还要把这个点相邻的big点的权值加到答案里去（因为此时sum[u]sum[u]中并不包含big点的权值）

m是边数，最大为100000
每个点最多有m300=300m300=300个big点。因此询问的时间复杂度也是O(k∗300)O(k∗300)
这样总的时间复杂度就是O(k∗300)O(k∗300)

这道题还没有做完

我们刚刚求的只是一轮循环节的答案，我们现在需要求极限值。

而第一轮的答案与第二轮的答案没有任何比例关系。

这迫使我们去寻找组成第一轮答案的部分与组成第二轮答案的部分之间有没有关系。

我们设顶点vv，初始权值为val[v]val[v],在第一轮中的贡献为x1x1,那么肯定有x1=p∗val[v]x1=p∗val[v]，其中p代表一个比例系数。

在第一轮以后，vv的权值变成了val[v]∗12cnt[v]val[v]∗12cnt[v]，其中cnt[v]cnt[v]表示的是这个vv点在循环节中出现的次数。

第二轮中vv对答案的贡献是x2x2，那么x2=p∗val[v]∗12cnt[v]x2=p∗val[v]∗12cnt[v]

这样推导下去，并对所有的xx求和得到

sumx=p∗val[v]1−2−cnt[v]sumx=p∗val[v]1−2−cnt[v]

关键点来了！！！
注意看sumxsumx与x1x1的形式关系，发现就相当于用val[v]1−2−cnt[v]val[v]1−2−cnt[v]替换了val[v]val[v]
因此，我们想到了解题方案，就是一开始就对所有点的权值按照这个关系进行替换，然后跑一轮循环节，得到的答案就是要求的极限。

这道题还没有做完
这道题不一定会有极限，如果没有极限，要输出-1。
怎么判定有没有极限呢？
如果一个点被访问了，那么周围点的权值都会被加到答案里面去，所以周围点的权值必须减少，如果发现一个点被访问了，而在循环节结束后，还有一个周围相邻的点的权值没有被减少，那么意味着肯定不会收敛。

终于讲完了，如果觉得好就点个赞吧。

代码

#include <iostream> #include <cstdio> #include <vector> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; #define pr(x) cout<<#x<<':'<<x<<endl const int maxn = 100007; ll n,m,k,val[maxn],s[maxn]; vector<int> G[maxn],heavy[maxn]; int deg[maxn],cnt[maxn],vis[maxn],big[maxn]; ll sum[maxn],ans[maxn]; const ll mod = 1e9+7; long long powmod(long long x, long long p){long long res = 1;while(p > 0){if(p % 2 == 1) res = res * x % mod;x = x * x % mod;p >>= 1;}return res; } ll mi[maxn],inv[maxn]; int main(){inv[0] = mi[0] = 1;for(int i = 1;i < maxn;++i)mi[i] = 2ll*mi[i-1]%mod;inv[1] = powmod(2,mod-2);for(int i = 2;i < maxn;++i)inv[i] = inv[1]*inv[i-1]%mod;scanf("%lld%lld%lld",&n,&m,&k);for(int i = 1;i <= n;++i)scanf("%lld",&val[i]);for(int i = 1;i <= k;++i)scanf("%lld",&s[i]);for(int i = 0;i < m;++i){int a,b;scanf("%d%d",&a,&b);G[a].push_back(b);G[b].push_back(a);deg[a]++;deg[b]++;}for(int i = 1;i <= n;++i)for(int j = 0;j < G[i].size();++j)if(deg[i] > 300) heavy[G[i][j]].push_back(i),big[i] = 1;for(int i = 1;i <= k;++i){cnt[s[i]]++;if(cnt[s[i]] == 1)for(int j = 0;j < G[i].size();++j)vis[G[i][j]] = 1;}for(int i = 1;i <= n;++i){if(vis[i] && !cnt[i] && val[i] > 0)return 0*puts("-1");}for(int i = 1;i <= n;++i){val[i] = val[i]*powmod((1-inv[cnt[i]]+mod)%mod,mod-2)%mod;}for(int i = 1;i <= n;++i){if(big[i]) continue;for(int j = 0;j < G[i].size();++j)sum[G[i][j]] = (sum[G[i][j]] + val[i])%mod;}ll res = 0;for(int i = 1;i <= k;++i){int u = s[i];res = (res + sum[u])%mod;for(int j = 0;j < heavy[u].size();++j){int v = heavy[u][j];res = (res + val[v])%mod;}ll old = val[u];val[u] = old*inv[1]%mod;//val[u] = val[u]*inv[1]%mod;if(!big[u]){for(int j = 0;j < G[u].size();++j){int v = G[u][j];sum[v] = (sum[v] - old + val[u] + mod)%mod;}} }cout<<res<<endl;return 0; }

总结

以上是生活随笔为你收集整理的codeforces gym-101745 C-Infinite Graph Game 分块的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。