题解 CF618G【Combining Slimes】
cyffff
2022-02-28 18:09:15
[$\text{Link}$](https://www.luogu.com.cn/problem/CF618G)
（这题过程很长，所以我直接把我写的 PPT 截图挂上来了。）
代码：
写代码的时间比较早，变量名与 PPT 中不同，仅供参考。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lf long double
namespace IO{//by cyffff
}
struct Matrix{
lf a[55][55];
Matrix(){ memset(a,0,sizeof(a)); }
inline lf* operator[](const int &x){
return a[x];
}
inline void epi(){
for(int i=0;i<50;i++)
a[i][i]=1;
}
inline friend Matrix operator*(Matrix a,Matrix b){
Matrix c;
for(int i=0;i<50;i++)
for(int j=0;j<50;j++)
for(int k=0;k<50;k++)
c.a[i][j]+=a.a[i][k]*b.a[k][j];
return c;
}
}A,B;
inline Matrix qpow(Matrix A,int b){
Matrix B;
B.epi();
while(b){
if(b&1) B=B*A;
A=A*A;
b>>=1;
}
return B;
}
/*
a(i,j)表示序列长度限制为i，最左侧出现j的概率。
b(i,j)表示序列长度限制为i，第一次出现的是2，最左侧出现j的概率。
*/
int n;
lf p,a[55][55],b[55][55],c[55][55],d[55][55],dp[55][55];
int main(){
scanf("%d %Lf",&n,&p);
p/=1e9;
a[1][1]=p;
a[1][2]=1-p;
b[1][2]=1-p;
for(int i=2;i<=50;i++){
a[i][1]=p;
a[i][2]=1-p+p*p;
b[i][2]=1-p;
for(int j=3;j<=50;j++)
a[i][j]=a[i][j-1]*a[i-1][j-1],
b[i][j]=b[i][j-1]*a[i-1][j-1];
}
for(int i=1;i<=50;i++)
for(int j=1;j<=50;j++)
c[i][j]=a[i][j]*(1-a[i-1][j]),
d[i][j]=b[i][j]*(1-a[i-1][j]);
dp[1][1]=1,dp[1][2]=2;
for(int i=2;i<=50;i++){
lf sum=0;
for(int k=2;k<=50;k++)
dp[i][1]+=dp[i-1][k]*d[i-1][k],sum+=d[i-1][k];
dp[i][1]=1+dp[i][1]/sum;
for(int j=2;j<=50;j++){
sum=0;
for(int k=1;k<j;k++)
dp[i][j]+=dp[i-1][k]*c[i-1][k],sum+=c[i-1][k];
dp[i][j]=j+dp[i][j]/sum;
}
}
if(n<=50){
lf ans=0;
for(int i=1;i<=n+1;i++)
ans+=dp[n][i]*c[n][i];
printf("%.6Lf",ans);
return 0;
}
A[0][0]=B[0][0]=1;
for(int i=1;i<=50;i++)
A[0][i]=dp[50][i];
lf sum=0;
for(int j=2;j<=50;j++)
B[j][1]+=d[50][j],sum+=d[50][j];
for(int j=2;j<=50;j++)
B[j][1]/=sum;
B[0][1]=1;
for(int i=2;i<=50;i++){
sum=0;
for(int j=1;j<i;j++)
B[j][i]+=c[50][j],sum+=c[50][j];
for(int j=1;j<i;j++)
B[j][i]/=sum;
B[0][i]=i;
}
A=A*qpow(B,n-50);
lf ans=0;
for(int i=1;i<=50;i++)
ans+=A[0][i]*c[50][i];
printf("%.6Lf",ans);
}
```
再见 qwq~