【题解】P6130 随机红包
鏡音リン
·
·
题解
2021/06/29 更新：添加了详细的推式子过程，以及修改了排版。
如果有人问我推过最恶心的式子是哪个，我会说是这题。
我就不打表找规律，推式子警告
我们设 f(n,k,x) 表示有 n 个人的情况下，第 k 小的红包钱数大于 x 的概率。这也等价于至少 n-k+1 个红包的钱数大于 x 的概率。这里推荐使用第二种定义，方便理解后面的递推边界。
那么，容易看出我们要求的答案 ans(n,k)=\int_0^1f(n,k,x)dx。
考虑 f 的递推式，n 个人时生成了 n-1 个随机数，设这些随机数里最小的那个是 v。此时一定有一个金额为 v 的红包，讨论 v 和 x 的大小关系：
如果 v<x，那么剩下 n-1 个红包里就需要 n-k+1 个红包大于 x；
如果 v>x，那么剩下 n-1 个红包里就需要 n-k 个红包大于 x。
再想想，“1-v 块钱分成 n-1 个红包有 n-k+1 个红包大于 x”和“1 块钱分成 n-1 个红包有 n-k+1 个红包大于 \frac{x}{1-v}”是一样的，可以理解为通货膨胀了（？）
还有一个问题，虽然随机数是均匀分布的，但 n-1 个随机数中的最小值 v 可不是均匀分布的。我们要求出这个最小值小于 v 的概率是 1-(1-v)^{n-1}，然后对它求导得到 (n-1)(1-v)^{n-2}，这个可以认为是最小值为 v 的相对概率
综合上述讨论，可以得到 f 的递推式
\begin{aligned}
&f(n,k,x)\\
=&(n-1)\int_0^x(1-v)^{n-2}f(n-1,k-1,\frac{x}{1-v})dv\\
+&(n-1)\int_x^1(1-v)^{n-2}f(n-1,k,\frac{x}{1-v})dv
\end{aligned}
开始积分
\begin{aligned}
&\int_0^1f(n,k,x)dx\\
=&(n-1)\int_0^1\int_0^x(1-v)^{n-2}f(n-1,k-1,\frac{x}{1-v})dvdx\\
+&(n-1)\int_0^1\int_x^1(1-v)^{n-2}f(n-1,k,\frac{x}{1-v})dvdx
\end{aligned}
设 t=\frac{x}{1-v} 然后化简一波，此处省略去了漫长的计算过程
\begin{aligned}
&\int_0^1f(n,k,x)dx\\
=&\frac{n-1}{n}\int_0^{+\infty} (1-\frac{1}{(t+1)^n})f(n-1,k-1,t)dt\\
+&\frac{n-1}{n}\int_0^{+\infty} \frac{1}{(t+1)^n}f(n-1,k-1,t)dt
\end{aligned}
注意这里积分上界变成了 {+\infty}，不是 1，因为 t 的范围可以到正无穷大，而且当 k=n+1,x>1 时 f(n,k,x) 仍然有意义且值为 1，所以一定要积到正无穷大！下面推边界的时候也有这方面的说明
貌似得到了更复杂的式子，出现了 \frac{1}{(t+1)^n} 这个因子，我们用同样的方法继续积分看看
\begin{aligned}
&\int_0^{+\infty} \frac{1}{(x+1)^{(n+1)}}f(n,k,x)dx\\
=&\frac{n-1}{n}\int_0^{+\infty} (\frac{1}{(t+1)^n}-\frac{1}{(2t+1)^n})f(n-1,k-1,t)dt\\
+&\frac{n-1}{n}\int_0^{+\infty} \frac{1}{(2t+1)^n}f(n-1,k-1,t)dt
\end{aligned}
事情逐渐清晰起来，可以猜想并证明：
\begin{aligned}
&\int_0^{+\infty} \frac{1}{(lx+1)^{(n+1)}}f(n,k,x)dx\\
=&\frac{n-1}{n}\int_0^{+\infty} (\frac{1}{(lt+1)^n}-\frac{1}{((l+1)t+1)^n})f(n-1,k-1,t)dt\\
+&\frac{n-1}{n}\int_0^{+\infty} \frac{1}{((l+1)t+1)^n}f(n-1,k-1,t)dt
\end{aligned}
这回可以递推了。设
P(n,k,l)=\int_0^{+\infty} \frac{1}{(lx+1)^{(n+1)}}f(n,k,x)dx
则有
P(n,k,l)=\frac{n-1}{n}(P(n-1,k-1,l)-P(n-1,k-1,l+1)+P(n-1,k,l+1))
递推边界通过 P 和 f 的定义可以计算：
P(n,k,l) =
\begin{cases}
0, & k=0; \\
\int_0^{+\infty} (lx+1)^{-n-1}dx=\frac{1}{ln}, & k=n+1;\\
\int_0^1 (lx+1)^{-2}dx=\frac{1}{l+1}, & n=1;\\
\end{cases}
这里为什么 n=1 时积到 1 而 k=n+1 时要积到 {+\infty} 呢，因为 x>1 时 f(1,1,x)=0，但是 k=n+1 时 f(n,k,x) 表示的是至少 0 个红包大于 x 的概率，那么无论 x 为何值 f(n,k,x) 的值都为 1
最终答案就是 P(n,k,0)。
那么这玩意怎么化简呢
首先我们看着 \frac{n-1}{n} 这个因子很难受，不妨修改一下 P 的定义，用 P(n,k,l) 表示之前 nP(n,k,l) 表示的意思，那么递推式和边界都要修改，顺便还能把递推式改为等价的更简洁的形式
P(n,k,l) =
\begin{cases}
0, & n=0,k\le0; \\
\frac{1}{l}, & n=0,k>0;\\
P(n-1,k-1,l)-P(n-1,k-1,l+1)+P(n-1,k,l+1), & n>0
\end{cases}
此时 ans(n,k)=\frac{1}{n}P(n,k,0)。
假设从 P(n,k,0) 递归到 n=0 共调用了 a 次 P(n-1,k-1,l) 分支，b 次 P(n-1,k-1,l+1) 分支，c 次 P(n-1,k,l+1) 分支。需要满足 a+b+c=n，a+b<k。那么这部分的贡献就是 \frac{n!(-1)^b}{a!b!c!(b+c)}，总和为
P(n,k,0)=\sum_{a+b+c=n,a+b<k} \frac{n!(-1)^b}{a!b!c!(b+c)}
继续化简
\begin{aligned}
P(n,k,0)=&\sum_{a+b+c=n,a+b<k} \frac{n!(-1)^b}{a!b!c!(b+c)}\\
=&\sum_{a=0}^{k-1} \frac{n!}{a!(n-a)}\sum_{b=0}^{k-a-1} (-1)^b\frac{1}{b!(n-a-b)!}\\
=&\sum_{a=0}^{k-1} \frac{n!}{a!(n-a)!(n-a)}(-1)^{k-a-1}C(n-a-1,k-a-1)\\
=&\frac{n!}{(n-k)!}\sum_{a=0}^{k-1} \frac{(-1)^{k-a-1}}{(n-a)^2a!(k-a-1)!}\\
=&\frac{n!}{(n-k)!}\frac{1}{(k-1)!}\sum_{a=0}^{k-1} (-1)^{k-a-1}C(k-1,a)(a-n)^{-2}\\
=&\frac{n!}{(n-k)!}\frac{1}{(k-1)!}\sum_{a=0}^{k-1} (-1)^{k-a-1}C(k-1,a)\sum_{j=0}^{\infty}C(-2,j)a^j(-n)^{-2-j}\\
=&\frac{n!}{(n-k)!}\sum_{j=0}^{\infty}C(-2,j)(-n)^{-2-j}\frac{1}{(k-1)!}\sum_{a=0}^{k-1} (-1)^{k-a-1}C(k-1,a)a^j\\
=&\frac{n!}{(n-k)!}\sum_{j=0}^{\infty}(j+1)n^{-2-j}S_2(j,k-1)
\end{aligned}
记 G_m(x) 是第二类斯特林数第 m 列的普通生成函数，G_m'(x) 为其导数。我们有：
G_m(x)=\sum_{i=0}^\infty S_2(i,m)x^i=\prod_{j=1}^m\frac{x}{1-jx}
G_m'(x)=\sum_{j=1}^m\frac{1}{x(1-jx)}G_m(x)
原式可以写成生成函数的形式：
\begin{aligned}
P(n,k,0)=&\frac{n!}{(n-k)!}\sum_{j=0}^{\infty}(j+1)n^{-2-j}S_2(j,k-1)\\
=&\frac{n!}{(n-k)!} (n^{-3}G_{k-1}'(\frac{1}{n})+n^{-2}G_{k-1}(\frac{1}{n}))\\
=&\frac{n!}{(n-k)!} n^{-2} (1+\sum_{j=1}^{k-1}\frac{n}{n-j})G_{k-1}(\frac{1}{n})\\
=&\frac{n!}{(n-k)!} n^{-1} (\sum_{l=n-k+1}^{n}\frac{1}{l})\prod_{j=1}^{k-1}\frac{1}{n-j}\\
=&\sum_{l=n-k+1}^{n}\frac{1}{l}
\end{aligned}
这回可以快速计算多组询问了。别忘了除以 n！！
ans(n,k)=\frac1n\sum_{l=n-k+1}^n\frac1l
提醒：比赛时遇到这种题果断打表找规律。