首页 > 基础资料 博客日记
不会说明你有抑郁症5
2026-04-14 08:30:01基础资料围观1次
本篇文章分享不会说明你有抑郁症5，对你有帮助的话记得收藏一下，看极客资料网收获更多编程知识
孩子们我来学文化课了。
给定一个正方体，初始有一只蚂蚁在正方体的一个顶点上。每步移动，蚂蚁都会沿着正方形的棱等概率随机爬到一个和当前顶点相邻的顶点上。问 \(2n\) 步之后蚂蚁爬回起点的概率。
画一张图吧：
图上随机游走也太坏了，我们先进行一步转化，发现上面的问题等价于下面的问题：
给定模 \(2\) 意义下的三元组 \((x,y,z)\)，初始 \(x=y=z=0\)，每次操作从 \(x,y,z\) 中等概率选取一个 \(+1\)，问进行 \(2n\) 次操作后三元组为 \((0,0,0)\) 的概率。
算概率直接算合法方案数除以总方案数，总方案数是 \(9^n\)，现在我们只需要考虑合法方案数。
设 \(x,y,z\) 的操作次数分别为 \(a,b,c\)，枚举 \(a,b,c\)，那么系数是一个多重集排列数，也就是说，合法方案数是：
\[\sum_{a+b+c=2n \land a,b,c\bmod 2=0} \binom{2n}{a,b,c}
\]
现在我们需要把上面的和式写成一个可以 \(O(1)\) 计算的形式。
起手生成函数，我们设：
\[F(x)=\sum_{i\bmod 2=0} \frac{1}{i!}x^i
\]
容易发现上面的和式是：
\[(2n)![x^{2n}]F(x)^3
\]
考察 \(F(x)\) 的封闭形式，我们知道：
\[e^x=\sum_{i} \frac{1}{i!} x^i
\]
\[e^{-x}=\sum_{i} \frac{1}{i!}(-1)^ix^i
\]
容易发现：
\[F(x)=\dfrac{e^x+e^{-x}}{2}
\]
那么将 \(F(x)^3\) 暴力展开，有：
\[F(x)^3=\frac{1}{8} (e^{3x}+3e^x+3e^{-x}+e^{-3x})
\]
因为 \(2n\bmod 2=0\)，那么这里可以把 \(e^{-x}\) 也看成 \(e^x\)，也就是：
\[F(x)^3=\frac{1}{4} (e^{3x}+3e^x)
\]
直接翻译封闭形式：
\[(2n)![x^{2n}]=\frac{9^n+3}{4}
\]
于是我们求出了合法方案数！我们计算一下概率：
\[\frac{9^n+3}{4\cdot 9^n}=\frac{1}{4}+\frac{3}{4\cdot 9^n}
\]
从这个概率来看，随着移动步数增加，蚂蚁回到原点的概率趋近于 \(\dfrac{1}{4}\)，但是我好像没想到靠谱的组合意义去解释这个东西。
文章来源:https://www.cnblogs.com/Kenma/p/19862801
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！
标签：
相关文章
最新发布
点击排行
本站推荐
