首先，题目中已经说得很明确了（按照常理也是）。 当有mmm个包，你第kkk个抢。k>mk>mk>m的话。显然，平时会显示：来晚了一步，红包已经被领完了\text{来晚了一步，红包已经被领完了}来晚了一步，红包已经被领完了 就是，已经被第mmm个及之前的人领完了。所以说，期望是000。
然后，看k<=mk<=mk<=m的时候。
我们构造一个函数f(a,b,c)表示剩余a元，还有b个包，你在第c个抢得到的期望f(a,b,c)\text{表示剩余a元，还有b个包，你在第c个抢得到的期望}f(a,b,c)表示剩余a元，还有b个包，你在第c个抢得到的期望
于是，我们就有一个期望的转移：
f(n,m,k)=m2n∗∫02nmf(n−x,m−1,k−1) dxf(n,m,k)=\frac{m}{2n}*\int_{0}^{\frac{2n}{m}}f(n-x,m-1,k-1) \ \ dxf(n,m,k)=2nm∗∫0m2nf(n−x,m−1,k−1) dx
特别的，当k=1k=1k=1时
f(a,b,1)=b2a∗∫02abx dxf(a,b,1)=\frac{b}{2a}*\int_{0}^{\frac{2a}{b}}x \ dxf(a,b,1)=2ab∗∫0b2ax dx
m=1m=1m=1时，我们这一类里，只有m=k=1m=k=1m=k=1，f(a,1,1)=af(a,1,1)=af(a,1,1)=a
然后我们展开来看：
当k!=mk!=mk!=m时:::
f(n,m,k)=m2n∗∫02nmm−12(n−x1)∫02(n−x1)m−1m−22(n−x1−x2) …… m−k+22(n−x1...−xk−2)∫02(n−x1...−xk−2)m−k+2m−k+12(n−x1...−xk−1)∫02(n−x1...−xk−1)m−k+1xk dxk dxk−1... dx1f(n,m,k)=\frac{m}{2n}*\int_{0}^{\frac{2n}{m}}\frac{m-1}{2(n-x_{1})}\int_{0}^{\frac{2(n-x_{1})}{m-1}}\frac{m-2}{2(n-x_{1}-x_{2})} \ …… \ \frac{m-k+2}{2(n-x_{1}...-x_{k-2})}\int_{0}^{\frac{2(n-x_{1}...-x_{k-2})}{m-k+2}}\frac{m-k+1}{2(n-x_{1}...-x_{k-1})}\int_{0}^{\frac{2(n-x_{1}...-x_{k-1})}{m-k+1}}x_{k} \ d_{x_{k}}\ d_{x_{k-1}} ... \ d_{x_{1}}f(n,m,k)=2nm∗∫0m2n2(n−x1)m−1∫0m−12(n−x1)2(n−x1−x2)m−2 …… 2(n−x1...−xk−2)m−k+2∫0m−k+22(n−x1...−xk−2)2(n−x1...−xk−1)m−k+1∫0m−k+12(n−x1...−xk−1)xk dxk dxk−1... dx1
当k=mk=mk=m时，积分到：
22(n−x1...−xm−2)∫02(n−x1...−xm−2)2xm−1 dxm−1 dxm−2... dx1\frac{2}{2(n-x_{1}...-x_{m-2})}\int_{0}^{\frac{2(n-x_{1}...-x_{m-2})}{2}} x_{m-1} \ d_{x_{m-1}}\ d_{x_{m-2}} ... \ d_{x_{1}}2(n−x1...−xm−2)2∫022(n−x1...−xm−2)xm−1 dxm−1 dxm−2... dx1
就可以了。
然后………………
这怎么做？！！！kkk重积分啊，套自适应性辛普森积分？
数据范围一看，TTT了啊。
好吧好吧，我们化简一下看看。
先只看后两项：
$\frac{m-k+2}{2(n-x_{1}…-x_{k-2})}\int_{0}{\frac{2(n-x_{1}…-x_{k-2})}{m-k+2}}\frac{m-k+1}{2(n-x_{1}…-x_{k-1})}\int_{0}{\frac{2(n-x_{1}…-x_{k-1})}{m-k+1}}x_{k} \ d_{x_{k}}\ d_{x_{k-1}} $
我们开始化简：
m−k+22(n−x1...−xk−2)∫02(n−x1...−xk−2)m−k+2m−k+12(n−x1...−xk−1)∗12∗[2(n−x1...−xk−1)m−k+1]2xk dxk dxk−1\frac{m-k+2}{2(n-x_{1}...-x_{k-2})}\int_{0}^{\frac{2(n-x_{1}...-x_{k-2})}{m-k+2}}\frac{m-k+1}{2(n-x_{1}...-x_{k-1})} *\frac{1}{2}*[ \frac{2(n-x_{1}...-x_{k-1})}{m-k+1} ]^{2} x_{k} \ d_{x_{k}}\ d_{x_{k-1}}2(n−x1...−xk−2)m−k+2∫0m−k+22(n−x1...−xk−2)2(n−x1...−xk−1)m−k+1∗21∗[m−k+12(n−x1...−xk−1)]2xk dxk dxk−1
m−k+22(n−x1...−xk−2)∫02(n−x1...−xk−2)m−k+2(n−x1...−xk−1)m−k+1\frac{m-k+2}{2(n-x_{1}...-x_{k-2})}\int_{0}^{\frac{2(n-x_{1}...-x_{k-2})}{m-k+2}} \frac{(n-x_{1}...-x_{k-1})}{m-k+1}2(n−x1...−xk−2)m−k+2∫0m−k+22(n−x1...−xk−2)m−k+1(n−x1...−xk−1)
然后，把常数1m−k+1\frac{1}{m-k+1}m−k+11提出来，继续拆一个积分号，这里就不写了。
希望自己找一张草稿纸写一下。
神奇的发现。
竟然是那么的相似。
我们很显然的利用数学归纳法。
直接按照相似的公式积第一项，把常数也按照规律写下来。
积分之后，把所有常数消去。
神奇的发现：
f(n,m,k)=nmf(n,m,k)=\frac{n}{m}f(n,m,k)=mn
mmp!!!mmp!!!mmp!!!
(感受到了世界的深深的恶意)
是不是我们算错了？
好，现在请拿起身边的卡西欧计算器。
我们试试样例一：
n=100,m=10,k=3n=100,m=10,k=3n=100,m=10,k=3
我们把k=1,2,3k=1,2,3k=1,2,3都试一下。
nm=10\ \frac{n}{m}=10 mn=10
k=1 :k=1 \ :k=1 :
f(100,10,1)=120 ∫020x dx=10f(100,10,1)=\frac{1}{20} \ \int_{0}^{20} x\ d_{x} =10f(100,10,1)=201 ∫020x dx=10
k=2 :k=2 \ :k=2 :
f(100,10,2)=120∫02092(100−x1)∫02(100−x1)9x2 dx2 dx1f(100,10,2)=\frac{1}{20}\int_{0}^{20} \frac{9}{2(100-x_{1})}\int_{0}^{\frac{2(100-x_{1})}{9}} x_{2}\ \ dx_{2} \ dx_{1}f(100,10,2)=201∫0202(100−x1)9∫092(100−x1)x2 dx2 dx1
=120∫020(100−x1)9 dx1 =1180∫020(100−x1) dx1=10=\frac{1}{20}\int_{0}^{20} \frac{(100-x_{1})}{9} \ dx_{1}\ =\frac{1}{180}\int_{0}^{20}(100-x_{1}) \ \ dx_{1}=10=201∫0209(100−x1) dx1 =1801∫020(100−x1) dx1=10
k=3 :k=3 \ :k=3 : 算出来也是101010
哇………………
好吧，这道题就是nm\frac{n}{m}mn了，O1O_{1}O1搞出来了。
ENDENDEND。
转载于:https://www.cnblogs.com/vercont/p/10210096.html
