思路

考虑区间 DP 。我们可以发现有一个很显然的 $O(n^3)$ 做法，我们反着做，设 $dp[i][j]$ 为第 $i$ 到第 $j$ 个细菌活下来的概率。转移就相当于把 $i$ 到 $j$ 这段区间切成了 $i$ 到 $k$ 和 $k+1$ 到 $j$ 这两段。

可以发现不管怎么切切出来的这两段里总会有一个继承 $dp[i][j]$ 的遗产，也就是 $\dfrac{dp[i][j]}{j-i}$ ，暴力做法就是枚举 $k$ 即可。

考虑优化，我们可以双指针预处理出一个临界点 $mid$ ，当 $k$ 在 $mid$ 左边时右半部分继承遗产，反之则左半部分继承遗产。

但是这样还是 $O(n^3)$ 的，我们考虑优化转移，维护两个差分数组，随着 $len$ 的下降一层一层向下传，这个差分的细节有点多，写的时候注意一点。最后复杂度 $O(n^2)$

代码

#include<bits/stdc++.h>//~~~∈ 这是鸡爪
//#pragma GCC optimize("Ofast,unroll-loops")
#define ll long long 
using namespace std;
const int mod=1e9+7;
int n,arr[5005],qsum[5005],mid[5005][5005],cf[5005][5005][2],inv[10005],dp[5005][5005];
int ksm(int x,int y){
    if(y==0)return 1;
    if(y==1)return x;
    int aa=ksm(x,y>>1);
    if(y&1){
        return (ll)aa*aa%mod*x%mod;
    }
    return (ll)aa*aa%mod;

}
void sol(){
    cin>>n;

    for(int i=1;i<=n;++i){
        cin>>arr[i];
        qsum[i]=qsum[i-1]+arr[i];
    }
    for(int i=1;i<=n;++i){
        int dq=i-1;
        for(int j=i;j<=n;++j){
            while(qsum[dq]-qsum[i-1]<=qsum[j]-qsum[dq]){
                ++dq;
            }
            mid[i][j]=dq;
        }
    }
    for(int i=1;i<=10000;++i){
        inv[i]=ksm(i,mod-2);
    }
    dp[1][n]=1;

    for(int l=n;l>=1;--l){
        for(int i=1;i<=n-l+1;++i){
            int j=i+l-1;
            cf[i][j][0]+=cf[i][j+1][0];
            cf[i][j][0]%=mod;
            cf[i][j][1]+=cf[i-1][j][1];
            cf[i][j][1]%=mod;
            dp[i][j]+=cf[i][j][0];
            dp[i][j]%=mod;
            dp[i][j]+=cf[i][j][1];
            dp[i][j]%=mod;
            
            int x=mid[i][j];
            int p=(ll)inv[l-1]*dp[i][j]%mod;
            cf[i][j][0]+=p;
            cf[i][j][0]%=mod;
            cf[i][mid[i][j]-1][0]-=p;
            cf[i][mid[i][j]-1][0]=(cf[i][mid[i][j]-1][0]+mod)%mod;
            cf[i][j][1]+=p;
            cf[i][j][1]%=mod;
            cf[mid[i][j]+1][j][1]-=p;
            cf[mid[i][j]+1][j][1]=(cf[mid[i][j]+1][j][1]+mod)%mod;
        }
    }
    for(int i=1;i<=n;++i){
        cout<<dp[i][i]<<'\n';
    }
}
signed main(){
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        sol();
    }

}
//