题解 CF618G【Combining Slimes】

· · 题解

\text{Link}

（这题过程很长，所以我直接把我写的 PPT 截图挂上来了。）

代码：

写代码的时间比较早，变量名与 PPT 中不同，仅供参考。

#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~