Luogu P3412 仓鼠找\(sugar\) \(II\)

题目大意：

给定一棵\(n\)个点的树，
仓鼠每次移动都会等概率选择一个与当前点相邻的点，并移动到此点。
现在随机生成一个起点、一个终点(可能相同)。
仓鼠希望知道它从起点走到终点的期望步数是多少。
数据范围：

对于\(30\%\)，\(n\leq 5\)
对于\(60\%\)，\(n\leq 5\times 10^3\)
对于\(100\%\)，\(n \leq 7\times 10^6\)

请将输出答案(一个分数)模上\(998244353\)。

思路与解法

比较套路的一题了......

那个\(30\%\)实在是不会，难道是手玩？

对于 \(60\%\) 的数据：

我们枚举一个树根。设\(f[x]\) 表示 由\(x\) 移动到 \(x\)的父亲\(fa\) 的期望步数。
转移老套路，同这里所介绍的递推式法：
\[f[u] = 1 + \frac{\sum_{v \in son\{u\}}(f[v] + f[u])}{degree(u)}\]
化简一波可得：
\[f[u] = degree(u) + \sum_{v \in son\{u\}} f[v]\]
所以枚举终点，并将终点作为根，然后\(DP\)一遍利用\(size\)统计答案。
时间复杂度\(O(n^2)\)，可以跑过\(60\%\)

对于 \(100\%\) 的数据：

其实都会\(60\%\)，\(100\%\)简直就是送的......
我们考虑一条边，经过它的路径只有两种情况：从下往上，从上往下。
从下往上的情况我们用上面的\(f[u]\)即可统计。
所以再算一遍从上往下的即可。
设\(g[v]\)表示 从v的父亲\(u\) 移动到 v 的期望步数
用一样的方法设计\(DP\)的转移即可：
\[g[v] = 1 + \frac{(g[u] + g[v]) + \sum_{i \in son\{u\}}^{i \neq v} (f[i] + g[v])}{degree[u]}\]
然后化简一波：
\[g[v] = degree(u) + g[u] + \sum_{i \in son\{u\}}^{i \neq v} f[i] \]
计算答案的公式(考虑路径贡献即可得到)：
\[ans = \frac{\sum_{i=1}^n (f[i]+g[i])\times size[i] \times (n - size[i])}{n^2}\]
所以就以 \(1\)号结点为根，只做一遍\(DP\)，最后统计答案即可，时间复杂度\(O(n)\)。

实现代码：

注：代码中，\(Work\)函数求\(f[u]\)，\(Work2\)函数求\(g[u]\)

#include<bits/stdc++.h>
#define RG register
#define IL inline
#define ll long long
#define _ 100005
#define mod 998244353
using namespace std;

IL int gi(){
    RG int data = 0 , m = 1; RG char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9'))ch = getchar();
    if(ch == '-'){m = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){data = (data << 1) + (data << 3) + (ch ^ 48); ch = getchar(); }
    return ( m ) ? data : -data;
} 

ll f[_],g[_],deg[_],n,m,ans,sz[_];
struct Road{int to , next;}t[2*_]; int head[_],cnt;

IL ll Pow(RG ll T , RG ll js , RG ll S){
    while(js){
        if(js & 1)S = S * T % mod;
        js >>= 1;  T = T * T % mod;
    }return S;
}
IL ll Inv(RG ll x){ return Pow(x , mod - 2 , 1); }

IL void Work(RG int u , RG int fa){
    RG ll b = 0; f[ u ] = 0; sz[u] = 1;
    for(RG int i = head[u] ; i ; i = t[i].next){
        RG int v = t[i].to; if(v == fa)continue;
        Work(v , u); b = b + f[ v ]; if(b >= mod)b -= mod;
        sz[u] += sz[v];
    }
    if(!fa)return;  if(!b){f[ u ] = 1; return;}
    f[ u ] = ( deg[ u ] + b ) ;  if( f[ u ] >= mod )f[ u ] -= mod;
}

IL void Work2(RG int u , RG int fa){
    RG ll b = 0;
    for(RG int i = head[u] ; i ; i = t[i].next){
        RG int v = t[i].to;  if(v == fa)continue;
        b = b + f[ v ];  if(b >= mod)b -= mod;
    }b = (b + g[ u ]) % mod;
    for(RG int i = head[u] ; i ; i = t[i].next){
        RG int v = t[i].to;  if(v == fa)continue;
        g[ v ] = ((deg[u] + b - f[v]) % mod + mod) % mod;
        Work2(v , u);
    }return;
}

int main(){
    freopen("testdata.in","r",stdin);
    n = gi();
    for(RG int i = 1; i <= n - 1; i ++){
        RG int u = gi() , v = gi();
        t[ ++ cnt ] = (Road){ v , head[u] }; head[u] = cnt;
        t[ ++ cnt ] = (Road){ u , head[v] }; head[v] = cnt;
        deg[ u ] ++;  deg[ v ] ++;
    }
    Work(1 , 0); g[1] = g[0] = 0; Work2(1 , 0);
    ans = 0;
    for(RG int i = 1; i <= n; i ++)
        ans = (ans + f[i] * sz[i] % mod * (n - sz[i]) % mod) % mod;
    for(RG int i = 1; i <= n; i ++)
        ans = (ans + g[i] * sz[i] % mod * (n - sz[i]) % mod) % mod;
    ans = ans * Inv(n * n % mod) % mod;
    cout << ans;  return 0;
}

随机推荐

IOS FMDB 获取数据库表和表中的数据
ios开发中,经常会用到数据库sqlite的知识,除了增,删,改,查之外,我们说说如何获取数据库中有多少表和表相关的内容. 前言跟数据库使用相关的一般的增删改查的语句,这里就不做解释了.在网上有很多 ...
&period;NET string字符串的截取、移除、替换、插入
在实际开发中经常要用到string的各种截取等操作,在这里总结自己认为经常出现的.NET 字符串的截取.移除.替换.插入操作,方面以后查阅. 前台代码: <%@ Page Language=&q ...
Qt里怎么处理二进制数据
Qt里有个专门的类QDataStream就是专门读写二进制数据的, 它与QByteArray搭配在网络编程中有奇效. 来个栗子: // write data QByteArray data; QDat ...
Quartz&period;Net与MVC结合定时任务
1.首先,我们打开Visual Studio 2015,创建一个ASP.NET MVC的Web应用程序项目. 2.然后通过程序包管理器控制台来安装Quartz.Net组件. Quartz.Net一个最 ...
SourceTree基本操作
下载地址:https://www.sourcetreeapp.com 1.从克隆远程仓库 2.填写git地址 3.克隆成功后会来点如下界面,点击testGitHub 4.scourceTree管理界面 ...
ORACLE远程连接数据库
1. sqlplus sqlnet.ora 文件格式NAMES.DIRECTORY_PATH= (TNSNAMES,HOSTNAME).客户端就会首先在tnsnames.ora文件中找orcl的记录. ...
导入已有的vmdk文件，发现网络无法连通
把以前的节点都删除了,重新载入镜像.发现每一个都ping不同,ifconfig发现eth0端口都没有打开.. 解决: 进入: vim /etc/sysconfig/network-scripts/if ...
用ios做的一个简单的记事本
#import "ViewController.h" @interface ViewController ()@property (weak, nonatomic) IBOutle ...
Xcode自定义字体不能应用的原因
想给UILabel换一个自定义的字体,从字体册选择兰亭黑: 然后选择在Finder中显示,找到字体文件为Lantinghei.ttc: 将其拷贝到项目中,在info.plist里添加字体支持key, ...
Redis的应用场景
最近做了个小项目是WebForm 做着做着发现前台的首页读取速度很慢,并且多个用户同时访问我的Sqlserver承受不住!之后就想到了Redis 代码如下: /// <summary> / ...

秒客网

Luogu P3412 仓鼠找$sugar$ $II$