当前位置:网站首页>HDU7016 Random Walk 2
HDU7016 Random Walk 2
2021-08-08 00:30:49 【mrclr】
Portal
What a pity , At the end of the game 10 Minutes pushed out , however 10 You can't finish Gaussian elimination in minutes .
There are many ideas for this question , A kind of problem solving , And another kind of big man in our team , And my own kind of . But I don't quite understand the other two ideas , So I can only record my thoughts here .
I did this problem according to the random walk model in the figure .
Let's start with \(1\) Number point . Make \(E(u)\) Said go \(u\), And the probability of going on ,\(f(u)\) Said go \(u\), And stop at \(u\) Probability . Being able to go on means that you can't be in \(u\), Stopping means that the last moment must be \(u\).
Then you can list the relationship :
\(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)\).
Notice the following constant term , Because at first \(1\) Number point , So there is \(P(1,1)\) The probability of stopping , Yes \(P(1,u)\) The probability of going to another point .( Just because of these constant terms, I don't understand , Pushed wrong and gave up )
\(E(u)\) The relationship between them can be solved by Gaussian elimination , You can get it by substituting in \(F(u)\) 了 .
Above is the starting point in \(1\) The situation of , So for the starting point \(x\) The situation of , We find that the coefficient matrix is the same , Only the rightmost column of the augmented matrix is different , Therefore, the augmented matrix can be written as \(n+n\) Column ,\(n\) Simultaneous solutions of two equations . So time complexity is \(O(n * n * 2n)\).
Of course , You can also list the matrix equations and find the inverse , The effect is the same .
版权声明
本文为[mrclr]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210808003020385a.html
边栏推荐
- 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!