Lightoj 1408 Batting Practice LightOJ - 1408(解方程....)

題意

有

p

p

p機率投偏球,問連續中

k

!

k_!

k!​次和連續不中

2

k_2

k2​次的期望擊球數

VJ傳送門

定義

f

[

i

]

f[i]

f[i]為連續打偏

i

i次,還需要的期望

g

g[i]

g[i]為連續打中

=

1

f[k_2]=g[k_1]=0

f[k2​]=g[k1​]=0

+

∗

(

−

)

f[i]=f[i+1]*p+g[1]*(1-p)+1

f[i]=f[i+1]∗p+g[1]∗(1−p)+1

可以發現

f[i]的轉移依賴于

g[1]

g[1]

g[i]的轉移依賴于

f[1]

f[1]

是以可以令

x

i

c

s

f[i]=xi_i*g[1]+cs_i

f[i]=xii​∗g[1]+csi​

其中

xi_i

xii​是

g[1]的系數,

cs_i

csi​是常數項展開遞推

對數組

g

g也如此,最後就可以解二進制一次方程

但是我們可以O(1)求而不需要遞推

令

x=g[1]*(1-p)+1

x=g[1]∗(1−p)+1

那麼

p

.

k

−

f[1]=x+x*p^1+x*p^2...+x*p^{k_2-1}

f[1]=x+x∗p1+x∗p2...+x∗pk2​−1

等比數列求和

(

g

[

]

∗

p

)

+

p

k

−

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

f[1]=1−p(g[1]∗(1−p)+1)∗(1−pk2​−1)​

#include <bits/stdc++.h>
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);
	}
}