Description

題面

Solution

生命值范圍比較小,首先維護每一個人在每個血量的概率,從而算出生存的概率,設為 \(a[i]\)
詢問時,只需要考慮生存的人數,可以 \(DP\)
設 \(g[i][j]\) 表示前 \(i\) 個人活了 \(j\) 個的概率
\(g[i][j]=g[i-1][j-1]*a[i]+g[i-1][j]*(1-a[i])\)

那么考慮每一個人時,我們對其他人做這個 \(DP\) 就行了,可以做 \(O(C*n^3)\)
實際上這是個生成函數 \((a[i]*x+1-a[i])\) ,最終求出的是每一個人的乘積,除掉 \(i\) 這個人的就是我們暴力求出來的 \(DP\) 數組

這樣的話是可逆的,我們減去 \((1-a[i])\) 的項,剩下的就都是 \(a[i]\) 的項了,逆推一下即可

#include<bits/stdc++.h> using namespace std; template<class T>void gi(T &x){int f;char c;for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f; } const int N=205,M=1005,mod=998244353; inline int qm(int x,int k){int sum=1;while(k){if(k&1)sum=1ll*sum*x%mod;x=1ll*x*x%mod;k>>=1;}return sum; } int f[N][M],n,m[N],Q,op,x,p,q,h[N],a[N],tot,c[N],g[N][N],inv[N],res[N]; inline void Modify(){gi(x);gi(p);gi(q);p=1ll*p*qm(q,mod-2)%mod;q=(1-p+mod)%mod;h[0]=(f[x][0]+1ll*f[x][1]*p)%mod;for(int i=m[x];i>=1;i--)h[i]=(1ll*f[x][i+1]*p+1ll*f[x][i]*q)%mod;for(int i=m[x];i>=0;i--)f[x][i]=h[i],h[i]=0; } inline void solve(){gi(tot);for(int i=1;i<=tot;i++){gi(x);a[i]=(1-f[x][0]+mod)%mod;}memset(g,0,sizeof(g));g[0][0]=1;for(int i=1;i<=tot;i++){g[i][0]=g[i-1][0]*(1-a[i]+mod)%mod;for(int j=0;j<=i;j++)g[i][j]=(1ll*g[i-1][j-1]*a[i]+1ll*g[i-1][j]*(1-a[i]+mod))%mod;}for(int i=1;i<=tot;i++){int I=qm(a[i],mod-2),ans=0;for(int j=1;j<=tot;j++)h[j]=g[tot][j];for(int j=tot;j>=1;j--){ans=(ans+1ll*I*h[j]%mod*inv[j])%mod;h[j-1]=(h[j-1]-1ll*h[j]*(1-a[i]+mod)%mod*I)%mod;h[j]=0;}if(ans<0)ans+=mod;ans=1ll*ans*a[i]%mod;printf("%d ",ans);}puts(""); } int main(){freopen("pp.in","r",stdin);freopen("pp.out","w",stdout);for(int i=1;i<N;i++)inv[i]=qm(i,mod-2);cin>>n;for(int i=1;i<=n;i++)gi(m[i]),f[i][m[i]]=1;cin>>Q;while(Q--){gi(op);if(op==0)Modify();else solve();}for(int i=1;i<=n;i++){int ans=0;for(int j=1;j<=m[i];j++)ans=(ans+1ll*f[i][j]*j)%mod;printf("%d ",ans);}return 0; }

轉載于:https://www.cnblogs.com/Yuzao/p/9058367.html

總結

以上是生活随笔為你收集整理的bzoj 5340: [Ctsc2018]假面的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。