PS.PKu上面已经有现成公式了.


题目意思不再累述

Q=1的时候,表示询问T内门会坏几次的期望
Q=2的时候表示询问T时间内***会被惩罚几次的期望(如果某次门被打开坏了，那么以后每开一次门,都会诶惩罚一次,坏的那次不算,即如只开了2次门，第1次开门被搞坏了，第2次开被惩罚了，所以这种情况下是被惩罚1次)


p表示开一次门门会坏的概率,q=1.0-p,Q=1.0/q,c(i,j)表示从i个中选j个数的方案(组合数)
Q=1
P(n,i)表示T时间内一共开了n次门，坏了i次.
P(n,i)=(nanda * T)^n / n!  * c(n,i) * p^i * q^(n-i) *exp(-nanda *T)

现在我们先算P(i,i) P(i+1,i) P(i+2,i)...P(m,i)..这些的和显然就是T时间内坏i次的概率
假设为P_bro(i)=P(i,i)+P(i+1,i)+...+P(m,i)+...
P_bro(i)=sigma{ (nanda * T)^j / j! *c(j,i) * p^i * q^(j-i) }*exp(-nanda *T) (j=i,i+1,....m....)
= (p/q)^i * sigma{ (nanda * T*q)^j / j! *c(j,i) } *exp(-nanda *T)(j=i,i+1,....m....)
=(p/q)^i * sigma{ (nanda * T*q)^j / j! *j!/i!/(i-j)! }*exp(-nanda *T) (j=i,i+1,....m....)
=(p/q)^i * sigma{ (nanda * T*q)^j /i!/(i-j)! }*exp(-nanda *T) (j=i,i+1,....m....)
=(p/q)^i /i! * sigma{ (nanda * T*q)^j /(i-j)! }*exp(-nanda *T) (j=i,i+1,....m....)
=(p/q*nanda * T*q)^i /i! * sigma{ (nanda * T*q)^(j-i) /(j-i)! } *exp(-nanda *T)(j=i,i+1,....m....)
====令j-i=k
=(p/q*nanda * T*q)^i /i! * sigma{ (nanda * T*q)^k /k! } *exp(-nanda *T)(k=0,1,2...)
====由e^x 的展开得到
=(p/q*nanda * T*q)^i /i! * exp(nanda * T*q)*exp(-nanda *T)


现在我们要求E_bro(i)表示坏i次的期望，显然
E_bro(i)=P_bro(i)*i
=(p*nanda * T)^i /(i-1)! * exp(nanda * T*q)*exp(-nanda *T)
现在求总其他
ans=sigma(E_bro(i)) (i=1,2,.....)
ans=sigma{(p*nanda * T)^i /(i-1)! * exp(nanda * T*q) }
=exp(nanda * T*q)*(p*nanda * T)*sigma{(p*nanda * T)^(i-1) /(i-1)!} (i>=1)
=exp(nanda * T*q)*(p*nanda * T)*exp(p*nanda * T)*exp(-nanda *T)
=(p*nanda * T)

其实利用泊松分布的期望也可以求解，写以上的东西几乎完全是由于想复习一下概率.


Q=2

类似的我们构造P(n,i)表示开了n次门,被惩罚了i次的概率,显然这个没有现成的公式来套了
P(n,i)=(nanda *T)^n / n! * q(n-i-1) * p *exp(-nanda*T)
为什么?因为你必须先得到开了n次门的概率,然后假设被惩罚了i次,那么门肯定是在第n-i个坏了,从n-i+1->n次，由于门已经坏了，所以每次都被惩罚，所以才是i次

现在E_pu(i)表示为被惩罚i次的概率,显然
E_pu(i)=P(i+1,i)+P(i+2,i)+P(i+3,i)+....
E_pu(i)=p *exp(-nanda*T)*sigma{(nanda *T)^n / n! * q(n-i-1)} (n>=i+1)
= p *exp(-nanda*T)/q^(i+1)*sigma{(nanda *T*q)^n / n!}
可以发现这样下去几乎推不出来(至少我没推出来)
于是我们可以换种思路
对于打开n次门,显然被惩罚的次数=1,2,...n-1
然后把对应的概率累加上去，这里我直接累加他们的期望了
在开n次的情况下
EE(n) = P(n,1)*1+P(n,2)*2+...+P(n,n-1)*(n-1)
=exp(-nanda*T)*p*(nanda *T*q)^n / n!*sigma{i /q^(i+1)} (i=1..n-1)

下面的重点是求
sigma{i/q^(i+1)} (i=1..n-1)
我们把常数q^2拉出来
EE(n) = exp(-nanda*T)*p*Q^2*(nanda *T*q)^n / n!*sigma{i*Q^(i-1) } (i=1..n-1)
显然我们可以先求sigma{Q^i} (i=1..n-1)
然后对和求导即可
这个和显然不难求
bufsigma=(Q^n- Q)/(Q-1)
求导
bufsigma' = [(nQ^(n-1)-1)*(Q-1) - (Q^n -Q)]/(Q-1)^2
=[nQ^n-nQ^(n-1)-Q+1-Q^n+Q]/(Q-1)^2
=[nQ^n-nQ^(n-1)-Q^n+1]/(Q-1)^2
(Q-1)^2是常数，拉到求和符号外面
EE(n) = exp(-nanda*T)*p*Q^2/(Q-1)^2*(nanda *T*q)^n / n!*[nQ^n-nQ^(n-1)-Q^n+1]
由于Q/(Q-1)=1/q/((1-q)/q)=1/p
所以
EE(n)=exp(-nanda*T)/p*(nanda *T*q)^n / n!*[nQ^n-nQ^(n-1)-Q^n+1]
前面一群常数看成C=exp(-nanda*T)/p
EE(n)=C*(nanda *T*q)^n / n!*[nQ^n-nQ^(n-1)-Q^n+1]
然后求答案
ans=sigma{EE(n)} (n=2,3,...)
=C*sigma{(nanda *T*q)^n / n!*[nQ^n-nQ^(n-1)-Q^n+1]}
=C*{sigma{(nanda *T*q)^n / n!*(nQ^n)}-sigma{(nanda *T*q)^n / n!*(nQ^(n-1))}-sigma{(nanda *T*q)^n / n!*Q^n}+sigma{(nanda *T*q)^n / n!}}
=C*{(nanda *T*q*Q)*sigma{(nanda *T*q*Q)^(n-1) / (n-1)!} -(nanda *T*q)*sigma{(nanda *T)^(n-1) / (n-1)!}-sigma{(nanda *T)^n / n!}+sigma{(nanda *T*q)^n / n!}}
=C*{(nanda *T)*(e^(nanda *T)-1)-(nanda *T*q)*(e^(nanda *T)-1)-(e^(nanda *T)-1-nanda *T)+(e^(nanda *T*q)-1-nanda *T*q)}
=C*{(nanda *T*p)*(e^(nanda *T)-1)-(e^(nanda *T)-1-nanda *T*q)+(e^(nanda *T*q)-1-nanda *T*q)}
=exp(-nanda*T)/p*{...}
=(nanda *T)*exp(-nanda*T)-exp(-nanda*T)*((e^(nanda *T)-1-nanda *T*q)-(e^(nanda *T*q)-1-nanda *T*q))/p
=(nanda *T)-exp(-nanda*T)*{e^(nanda *T)-1-nanda *T*q-e^(nanda *T*q)+1+nanda *T*q}/p
=(nanda *T) -exp(-nanda*T)*{e^(nanda *T)-e^(nanda *T*q)}/p
=(nanda *T) -{1-e^(-nanda *T*p)}/p
=(nanda *T)+{e^(-nanda *T*p)-1}/p
完毕

• 赞...其实这道题最后设个浮点误差陷阱挺不厚道的，可是考虑到有种叫做mathematica的邪恶工具不得不这样了... (3900) moonancient 2009-09-21 17:12:28
• 后面写错了..sorry (812) majia5 2009-09-21 17:23:37
  • Re:后面写错了..sorry (2) acm_newer 2009-09-21 19:00:21
• Re:A的推导全过程 (31) Fanazhe 2009-09-21 19:10:27
  • 怎么推的，能不能发到我邮箱 (37) snO_Onz 2009-09-21 19:13:16
    • 铜球 (0) majia5 2009-09-21 19:20:30