【HDU4652】Dice（概率生成函数）

点此看题面

• 有一个\(m\)面的骰子，投出每一面的概率均等，求最后\(n\)次结果完全相同/不同时的期望投掷次数。
• 数据组数\(\le100,n,m\le10^6\)

概率生成函数

可见这篇博客：生成函数学习笔记（三）——概率生成函数初探。

总而言之是一个比较诡异的科技。

期望等于\(F‘(1)\)

我们设\(f_i\)表示序列最终长度为\(i\)的概率，并定义辅助序列\(g_i\)表示序列长度到达\(i\)不结束的概率。

由于\(F‘(1)=\sum_{i=0}^{+\infty}iP(X=i)=E(X)\)，所以我们就是要想办法表示出\(F‘(1)\)。

我们先列出一个很基本的式子：

简单解释一下，对于第一个式子，容易发现\(F(x)+G(x)\)的第\(i\)项是序列长度能达到\(i\)的概率，而\(xG(x)\)的第\(i\)项是序列长度为\(i-1\)时不结束的概率，显然两者等价，而\(1\)用于补足常数项。

我们对两边同时求导，然后代入\(x=1\)就会发现：

因此，\(E(X)=F‘(1)=G(1)\)。

最后\(n\)次结果相同

考虑我们连续加上\(m\)个相同字符（有\(m\)种方案）必然能达成条件，但也有可能提前达成条件，在一个已合法的情况后面又加上了\(n-i\)个相同字符。

因此列出式子：

由于我们要求\(G(1)\)，直接代入\(x=1\)即可解出：

最后\(n\)次结果不同

考虑我们连续加上\(m\)个不同字符（有\(\frac{m!}{(m-n)!}\)种方案）必然能达成条件，但也有可能提前达成条件，在一个已合法的情况后面又加上了\(n-i\)个不同字符（有\(\frac{(m-i)!}{(m-n)!}\)种方案）。

因此列出式子：

同样直接代入\(x=1\)即可解出：

代码：\(O(Tn)\)

#include<cstdio>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define DB double
using namespace std;
int n,m;I DB Calc0(CI n,CI m) {DB p=1;for(RI i=1;i<=n;++i) p*=m;return (p-1)/(m-1);}//最后n次相同
I DB Calc1(CI n,CI m) {DB t=0,p=1;for(RI i=1;i<=n;++i) p*=1.0*m/(m-i+1),t+=p;return t;}//最后n次不同
int main()
{
	RI Tt,op;scanf("%d",&Tt);W(Tt--) scanf("%d%d%d",&op,&m,&n),printf("%.10lf\n",op?Calc1(n,m):Calc0(n,m));return 0;
}

【HDU4652】Dice（概率生成函数）

原文：https://www.cnblogs.com/chenxiaoran666/p/HDU4652.html