牛客網wannafly挑戦試合23 C収益

のぞみリュックDP
複雑度(O(n*m))
先日模擬試験でこの問題を受けた
試験の時、どのように状態を設計するかを考えたが、残念ながら移行方程式が間違っていた.
私の考え:(dp[i][j])は前i個人がj元借りたときの期待支出を表し、(pp[i][j])は前i個人がj元借りた確率を表し、(ans=sum_{i=L}^{sum}pp[n][i]*(M-dp[n][i]))は(実際に私の試験場でMを乗る確率を忘れてしまった)
しかし、このような問題は、前のi人がj元を借りる確率が(100%)のときの期待支出であることを計算しなければならないことであり、移転するのは面倒(できるようだが、今後試験の際はできるだけ避けるべきだ)なので、j元を借りる確率も期待の一部として乗じなければならないことだ.
最後の方程式は次のように長いです.
\[pp[i][j]=p[i]×pp[i–1][j–m[i]]+(1–p[i])×pp[i–1][j]\]\[dp[i][j]=(1–p[i])×dp[i–1][j]+p[i]×(dp[i–1][j–m[i]]+pp[i–1][j–m[i]]×m[i]×r[i])\]
2番目のdp式をどのように理解しますか?
我々は(dp[i][j])が前(i)個人が(j)元を借りたときの期待支出*(pp[i][j])を表すことを発見した.
令(f[i][j])は、前i個人がj元を借りたときの期待支出を表す
つまり、[f[i][j]*pp[i][j]=(1-p[i])*pp[i-1][j]*f[i-1][j]+p[i]*pp[i-1][j-m[i]*(f[i-1][j-m[i]+[i]*m[i]*r[i])]という玄学的な式が解釈できるようになった

il int mns(int a,int b){
    return a-b<0?a-b+mod:a-b;
}

il int qpow(int x,int p) {
    int ans=1;
    for(; p; p>>=1) {
        if(p&1) ans=ans*x%mod;
        x=x*x%mod;
    }
    return ans;
}

signed main() {
    //freopen("input.txt","r",stdin);
    read(n),read(L),read(mon);
    int _100=qpow(100,mod-2);
    go(i,1,n)
    read(m[i]),read(r[i]),read(p[i]),sum+=m[i];
    go(i,1,n) {
        r[i]=r[i]*_100%mod;
        p[i]=p[i]*_100%mod;
    }
    pp[0]=1;
    go(i,1,n){
        com(j,sum,m[i]){
            pp[j]=(pp[j]*mns(1,p[i])%mod+pp[j-m[i]]*p[i]%mod)%mod;
            dp[j]=(dp[j]*mns(1,p[i])+(r[i]*m[i]%mod*pp[j-m[i]]%mod+dp[j-m[i]])%mod*p[i])%mod;
        }
        com(j,m[i]-1,0){
            pp[j]=pp[j]*mns(1,p[i])%mod;
            dp[j]=dp[j]*mns(1,p[i])%mod;
        }
    }
    int ans=0;
    go(i,L,sum) ans=(ans+mon*pp[i]%mod-dp[i])%mod;
    cout<