本文共 1714 字，大约阅读时间需要 5 分钟。

题意

有$p$概率投偏球,问连续中$k_{!}$次和连续不中$k_2$次的期望击球数

定义$f[i]$为连续打偏$i$次,还需要的期望

定义$g[i]$为连续打中$i$次,还需要的期望

$f[k_2]=g[k_1]=0$

$f[i]=f[i+1]\ast p+g[1]\ast (1-p)+1$

可以发现$f[i]$的转移依赖于$g[1]$

$g[i]$的转移依赖于$f[1]$

所以可以令$f[i]=x{i}_i\ast g[1]+c{s}_i$

其中$x{i}_i$是$g[1]$的系数,$c{s}_i$是常数项展开递推

对数组$g$也如此,最后就可以解二元一次方程

但是我们可以O(1)求而不需要递推

令$x=g[1]\ast (1-p)+1$

那么$f[1]=x+x\ast p^1+x\ast p^2...+x\ast p^{k_2-1}$

等比数列求和

$f[1]=\frac{(g[1]\ast (1-p)+1)\ast (1-p^{k_2-1})}{1-p}$

同理

$g[1]=\frac{(f[1]\ast p+1)\ast (1-(1-p{)}^{k_1-1})}{p}$

然后,我就感觉我的解方程白学了…

#include 
   
    using namespace std;const int maxn = 2e5+10;double xi[maxn],cs[maxn];double x[maxn],s[maxn],p;int main(){
   	int n,t,casenum=0,k1,k2;	cin >> t;	while( t-- )	{
   		cin >> p >> k1 >> k2;		//p概率出局 		xi[k2]=cs[k2]=x[k1]=s[k1]=0;		for(int i=k2-1;i>=1;i--)//出局 		{
   			xi[i] = xi[i+1]*p+(1.0-p);			cs[i] = cs[i+1]*p+1.0;		}		//f[1]=xi[1]*g[1]+cs[1]		for(int i=k1-1;i>=1;i--)//不出局 		{
   			x[i]=x[i+1]*(1-p)+p;			s[i]=s[i+1]*(1-p)+1.0;		}		//g[1]=x[1]*f[1]+s[1]		cs[1]+=xi[1]*s[1]; xi[1]*=x[1];		xi[1]-=1.0;		double f1=0;		if( xi[1]!=0 )	f1=-(cs[1]/xi[1]);		double g1 = x[1]*f1+s[1];		printf("Case %d: %.3lf\n",++casenum,f1*p+g1*(1.0-p)+1);	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109378195 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！