当前位置:网站首页>HDU7016 Random Walk 2
HDU7016 Random Walk 2
2021-08-08 00:30:27 【mrclr】
传送门
这题真可惜,比赛的时候最后10分钟推出来了,但是10分钟写不完高斯消元啊。
这题思路还挺多,有题解的一种,还有我们队里大佬的另一种,以及我自己的一种。但是其他两个思路我都不是很懂,遂只能将自己的思路记录于此了。
这题我就是按照图上的随机游走模型去做的。
我们先把起点选择在\(1\)号点。令\(E(u)\)表示走到\(u\),且能继续走下去的概率,\(f(u)\)表示走到\(u\),且停在\(u\)的概率。能继续走下去就意味着上一时刻不能在\(u\),停住就意味着上一时刻必须在\(u\).
那么可以列出关系式:
\(F(u)=E(u) * P(u,u) + P(1,1)*(u == 1)\),
\(E(u)=\sum\limits_{v = 1,v \neq u} ^ {n} E(v) * P(v, u) + P(1,u) * (u \neq 1)\).
注意后面的常数项,因为刚开始在\(1\)号点,所以有\(P(1,1)\)的概率停住,有\(P(1,u)\)的概率走到别的点。(就因为这些常数项我没整明白,推不对又放弃了)
\(E(u)\)之间的关系可以用高斯消元来解,代入就能求得\(F(u)\)了。
上面是起点在\(1\)的情况,那么对于起点在\(x\)的情况,我们发现系数矩阵是一样的,只有增广矩阵的最右边一列是不一样的,因此可以将增广矩阵写成\(n+n\)列,\(n\)个方程组同时解。那么时间复杂度就是\(O(n * n * 2n)\).
当然,也可以把矩阵方程列出来然后求逆,效果一样。
版权声明
本文为[mrclr]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15234622/3310234
边栏推荐
- Fourth in the world! Wang Sicong installed a server "readily". Netizen: trench is inhuman
- [Tencent classroom] creator zero foundation immortal practice is online!
- 跟着华为,学数字化转型(3):模式创新
- 记一次接口慢查排查
- Follow Huawei and learn digital transformation (3): mode innovation
- Record an interface slow check and troubleshooting
- @Autowired的这些骚操作,你都知道吗?
- ss -h命令
- @Do you know all these operations of Autowired?
- 使用Yolo v5进行目标检测
猜你喜欢
-
Yazid的新生舞会(线段树)
-
当creator遇上protobufjs|孕育
-
Identify and stop the process that‘s listening on port 8080 or configure this application to listen
-
为什么要推荐大家学习字节码?
-
揭秘!价值百万的像素填色解决方案,想开发绘本应用的有福了!
-
[PyTroch系列-11]:PyTorch基础 - 张量Tensor元素的排序
-
[PyTroch系列-12]:PyTorch基础 - 张量Tensor线性运算(点乘、叉乘)
-
【环境篇】第 3 节 • Navicat 环境安装
-
预训练语言模型的前世今生 - 从Word Embedding到BERT
-
讲道理,只要你是一个爱折腾的程序员,毕业找工作真的不需要再花钱培训!
随机推荐
- 华南理工 | 基于生成式的低比特无数据量化
- 微信小程序授权位置和用户信息权限(防止用户禁止后无法使用位置信息)
- 一行代码快速实现今日头条 网易新闻焦点图自动循环轮播效果
- 因果涌现:数学理论揭示整体怎样大于部分之和
- 年收入百万美元AI科学家的烦恼
- API《为什么奥运会以五色环为标志?》数据源接口
- 用一张草图创建GAN模型,新手也能玩转,朱俊彦团队新研究入选ICCV 2021
- UIUC | 用于语言模型的课程学习
- SS - H command
- Target detection using Yolo V5
- Yazid's freshman ball (thread tree)
- When creator meets protobufjs 𞓜
- 我敢肯定!你还没用过一款代码神器,只属于Creator的用户!
- 小程序页面跳转&&文章详情页的实现&&markdown格式转化为wxml显示在小程序页面里
- 49个项目管理过程ITTO整理(详细)
- 49个项目管理过程ITTO整理(详细-文字版)
- 只是想虐下春丽,一不小心撸了台游戏机...
- Cocos论坛九问九答
- Identify and stop the process that‘s listening on port 8080 or configure this application to listen
- 超详细的I/O多路复用概念、常用I/O模型、系统调用等介绍
- Why recommend learning bytecode?
- SAP Commerce Cloud UI 的用户会话管理
- 以太坊 交易 data字段 内容是什么
- SAP CRM Fiori 应用 My Note 里创建 Note 失败的一个原因分析
- 当creator遇上protobufjs|pbkiller填坑历险记
- Uncover the secret! Millions of pixel color filling solutions. Blessed are those who want to develop picture book applications!
- [pytroch series - 11]: pytorch basis - ordering of tensor tensor elements
- [pytroch series - 12]: pytorch basis tensor tensor linear operation (point multiplication, cross multiplication)
- [environment] section 3 • Navicat environment installation
- The past and present life of pre training language model - from word embedding to Bert
- Make sense, as long as you are a tossing programmer, you really don't need to spend money on training to find a job after graduation!
- South China Technology | low bit no data quantization based on generative
- Wechat applet authorizes location and user information permissions (to prevent users from being unable to use location information after prohibition)
- One line of code can quickly realize the automatic circular rotation effect of today's headlines and Netease News focus map
- Causal emergence: mathematical theory reveals how the whole is greater than the sum of parts
- The troubles of AI scientists with an annual income of millions of dollars
- API "why is the Olympic Games marked by five color rings?" Data source interface
- Create a GaN model with a sketch, which can be played by novices. The new research of Zhu Junyan's team was selected into iccv 2021
- UIUC | course learning for language model
- I'm sure! You haven't used a code artifact yet. It only belongs to creator users!