M_sea

CF248E Piglet's Birthday
CodeForcesLuogu翻译分析设$f[i][j]$表示第$i$个架子,有$j$个蜜罐没有被吃过的期望。设$...
扫描右侧二维码阅读全文
04
2019/01

CF248E Piglet's Birthday

CodeForces

Luogu翻译

分析

设$f[i][j]$表示第$i$个架子,有$j$个蜜罐没有被吃过的期望。

设$b[i]$为第$i$个架子上有的蜜罐数。

容易得到状态转移方程$\large f[u][i]=\sum\limits_{j=0}^kf[u][i+j]\times C_{i+j}^j\times C_{b[u]-i-j}^{k-j}\div C_{b[u]}^{k}$。

自己理解一下就好。

然后每次移动就将$b[u]$减去$k$,将$b[v]$加上$k$。

可以预处理出组合数,然后我成功的卡到了Luogu rk1

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;
const int MAXM=1000+10;
const int MAXA=100+10;

int n,q;
double ans;
int a[MAXN],b[MAXN];
double C[MAXM][MAXM];
double f[MAXN][MAXA]; //f[i][j]表示第i个架子,有j个蜜罐没有被吃过的期望

inline void getC() {
    C[0][0]=1;
    for (re int i=1;i<MAXM;++i) {
        C[i][0]=1;
        for (re int j=1;j<=i;++j)
            C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
}

inline void solve() {
    int u=read(),v=read(),k=read(); //u->v
    ans-=f[u][0];
    for (re int i=0;i<=a[u];++i) {
        double tmp=0;
        for (re int j=0;j<=k;++j)
            tmp+=f[u][i+j]*C[i+j][j]*C[b[u]-i-j][k-j]/C[b[u]][k];
        f[u][i]=tmp;
    }
    b[u]-=k,b[v]+=k,ans+=f[u][0];
    printf("%.12lf\n",ans);
}

int main() {
    getC();
    n=read();
    for (re int i=1;i<=n;++i) a[i]=b[i]=read();
    for (re int i=1;i<=n;++i) f[i][a[i]]=1,ans+=f[i][0];
    q=read();
    while (q--) solve();
    return 0;
}
最后修改:2019 年 05 月 26 日 04 : 00 PM

发表评论