description
偶然间,chnlich 发现了他小时候玩过的一个游戏“魂斗罗”,于是决定怀旧。但是这是一个奇怪的魂斗罗 MOD。
有 N 个关卡,初始有 Q 条命。
每通过一个关卡,会得到 u 分和1条命,生命上限为 Q。其中 u=min(最近一次连续通过的关数,R)。
若没有通过这个关卡,将会失去1条命,并进入下一个关卡。
当没有生命或没有未挑战过的关卡时,游戏结束,得到的分数为每关得到的分数的总和。
由于 chnlich 好久不玩这个游戏了,每条命通过每个关卡的概率均为p(0<=p<=1),原先 chnlich 的最高分纪录是 S。
现在 chnlich 想要知道,当 p 至少为多少时,chnlich 期望获得的总分数能够超过原先的最高分。
analysis
-
很好的二分(+)矩乘(+DP)题
-
由题解可得(50pts)的(DP)方程
[g[i+1][min(j+1,R)][min(k+1),Q]+=g[i][j][k]*p
]
[g[i+1][0][k-1]+=g[i][j][k]*(1-p)
]
[Answer+=g[i][j][k]*p*(j+1)
]
-
二分一个最小可能的(p)，用矩乘判断是否可行
-
对于每一种积分(x)命(y)条的状态，用不同的数字表示来压状态
-
可以知道当积分(≥q)时（连赢至少(q)次），命一定为(q)条，这样可以省去很多状态
-
压完状态之后，就只有(30)种左右的状态，可以矩乘快速幂
-
具体就是把按照方程每种状态转移到其他状态的矩阵位置加上贡献(p,1-p)或(p*(j+1))
-
注意那个(Answer)由所有的情况累加到最终状态，即为积分(0)命(0)条的情况
-
判断最终矩阵第起始状态行（积分(0)命(q)条）第终止状态列（积分(0)命(0)条）的值是否大于(s)即可
-
下次遇到矩乘题目，要认真想想(DP)，不要被矩阵怎么推给卡住
code
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 40
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)
using namespace std;
ll statu[10][50];
ll n,m,r,q,s;
struct matrix
{
double f[MAXN][MAXN];
matrix(){memset(f,0,sizeof(f));}
};
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline ll max(ll x,ll y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
inline matrix operator*(matrix a,matrix b)
{
matrix c;
fo(i,1,n)fo(j,1,n)fo(k,1,n)c.f[i][j]+=a.f[i][k]*b.f[k][j];
return c;
}
inline matrix pow(matrix x,ll y)
{
matrix z;
fo(i,1,n)z.f[i][i]=1;
if (y==0)return z;
while (y)
{
if (y&1)z=z*x;
x=x*x,y>>=1;
}
return z;
}
inline bool judge(double p)
{
matrix a;n=0;
fo(i,0,q)//statu[i][j]表示剩i条命有j积分的情况
{
ll tmp=i==q?r:min(i-1,r);
fo(j,0,max(tmp,0))statu[i][j]=++n;
}
a.f[1][1]=1;
fo(i,1,q)
{
ll tmp=i==q?r:min(i-1,r);
fo(j,0,max(tmp,0))
{
ll x=statu[i][j],y=statu[i-1][0],z=statu[min(i+1,q)][min(j+1,r)];
if (i>1)a.f[x][y]=1-p;a.f[x][z]=p,a.f[x][statu[0][0]]=p*min(j+1,r);
}
}
matrix b=pow(a,m);
return b.f[statu[q][0]][statu[0][0]]>s;
}
int main()
{
freopen("T2.in","r",stdin);
m=read(),r=read(),q=read(),s=read();
if (!judge(1)){printf("Impossible.
");return 0;}
ll l=0,r=10000000,tmp=r,mid=(l+r)>>1;
while (l<=r)
{
mid=(l+r)>>1;
if (judge(1.0*mid/tmp))r=mid-1;else l=mid+1;
}
printf("%.6lf
",1.0*l/tmp);
return 0;
}