P4564 [CTSC2018]假面

首先容易看出結界技能對第二問敵方剩余生命值期望沒有影響。

如何求出第$i$個人的剩余生命值期望？
只需要根據$E_i={\sum }_{j=0}^{a_i}j\times f_{i,j}$
預處理$f_{i,j}$：第$i$個人的剩余生命值為$j$的期望（$a_i$表示最初生命值）

由于每次鎖定技能只能明確對一名地方單位造成攻擊（$p$概率擊中而$q$概率不中），每次只需要$O(a_i)$的代價維護$f_{i,j}$總的時間復雜度$O(Qm)$
轉移方程：$f_{i,j}=p{f}_{i,j+1}+q{f}_{i,j}$，注意$f_{i,0}=p{f}_{i,1}+f_{i,0}$

---

對于第二個技能，想要知道命中$u$的概率，我們需要知道除了u之外還有$j$個人存活下，不妨叫做$g_{u,j}$。

只需要把除了$u$的其他敵人$v$拿出來跑一遍背包即可（注意逆序）
$g_{u,j}={\text{alive}}_v\times g_{u,j?1}+{\text{dead}}_v\times g_{u,j}$

顯然${\text{alive}}_v=1?f_{v,0}$：v存活下來的概率，${\text{dead}}_v=f_{v,0}$死了的概率。

對于第二個技能范圍的每個敵人，我們都需要預處理一下$g_{u,j}$數組，也就是$O(n^3)$的復雜度，第二個技能總時間復雜度$O(C{n}^3)$，代碼如下這時候我們能夠拿到$70$pts，$O(Qm+C{n}^3)$

#include<cstring> #include<iostream> using namespace std; using ll=long long; constexpr ll mod=998244353; ll qmi(ll a,ll b) {ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res; } ll inv[205],a[205],b[205]; ll f[205][105];//f[i][j]第i個人還有j滴血的概率 ll g[205];//將u那一維壓縮了 int n,m; void attack(int i,ll p)//O(qc) {ll q=(1-p+mod)%mod;for(int j=0;j<=a[i];j++){if(j)f[i][j]=(p*f[i][j+1]%mod+q*f[i][j]%mod)%mod;elsef[i][j]=(p*f[i][j+1]%mod+f[i][j])%mod;} } void solve(int k)//O(n^3) {for(int u=1;u<=k;u++)//枚舉范圍呢的每一個敵人{memset(g,0,sizeof g);g[0]=1ll;for(int i=1;i<=k;i++)//除了u的敵人跑一邊背包{if(u==i) continue;ll alive=((1ll-f[b[i]][0])%mod+mod)%mod;ll dead=((1ll-alive)%mod+mod)%mod;for(int j=i;j>=0;j--)//逆序！{if(j) g[j]=(g[j]*dead+g[j-1]*alive%mod)%mod;else g[j]=g[j]*dead%mod;}}ll ans=0;for(int j=0;j<k;j++) ans=(ans+g[j]*inv[j+1]%mod)%mod;ans=ans*((1ll-f[b[u]][0])%mod+mod)%mod;cout<<ans<<' ';}cout<<'\n'; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];inv[i]=qmi(i,mod-2);f[i][a[i]]=1;}cin>>m;while(m--){int op;cin>>op;if(op==0){int id;ll u,v;cin>>id>>u>>v;attack(id,1ll*u*qmi(v,mod-2)%mod);}else{int k;cin>>k;for(int i=1;i<=k;i++) cin>>b[i];solve(k);}}for(int i=1;i<=n;i++){ll ans=0;for(int j=1;j<=a[i];j++)ans=(ans+j*f[i][j]%mod)%mod;cout<<ans<<' ';}return 0; }

考慮優化，顯然我們TLE是由于第二個操作，如果每次枚舉然后跑背包似乎有些冗余。我們另設$g_j$表示$j$個人或者的概率，而用$h_{u,j}$表示除了u之外還有$j$個人存活下（也就是上面的$g_{u,j}$）有下面遞推
$$g_j={\text{alive}}_u\times h_{u,j?1}+{\text{dead}}_u\times h_{u,j}$$
于是有$$h_{u,j}=\frac{g_j?{\text{alive}}_u\times h_{u,j?1}}{{\text{dead}}_u}$$
于是我們只需要$O(n^2)$預處理$g_j$，然后枚舉$u$線性求出$h_{u,j}$同樣時間復雜度$O(n^2)$，那么技能二時間復雜度$O(C{n}^2)$

注意$g_j={\text{alive}}_u\times h_{u,j?1},{\text{dead}}_u=0$
即存在$h_{u,j}=g_{j+1}$

總時間復雜度$O(Qm+C{n}^2)$

#include<cstring> #include<iostream> using namespace std; using ll=long long; constexpr ll mod=998244353; ll qmi(ll a,ll b) {ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res; } ll inv[205],a[205],b[205]; ll f[205][105]; ll g[205],h[205];//h同樣可以少一維 int n,m; void attack(int i,ll p)//O(qc) {ll q=(1-p+mod)%mod;for(int j=0;j<=a[i];j++){if(j)f[i][j]=(p*f[i][j+1]%mod+q*f[i][j]%mod)%mod;elsef[i][j]=(p*f[i][j+1]%mod+f[i][j])%mod;} } void solve(int k) {memset(g,0,sizeof g);g[0]=1ll;for(int i=1;i<=k;i++)//預處理 g{ll alive=((1ll-f[b[i]][0])%mod+mod)%mod;ll dead=((1ll-alive)%mod+mod)%mod;for(int j=i;j>=0;j--){if(j) g[j]=(g[j]*dead+g[j-1]*alive%mod)%mod;else g[j]=g[j]*dead%mod;}}for(int u=1;u<=k;u++){ll ans=0;ll alive=((1ll-f[b[u]][0])%mod+mod)%mod;ll dead=((1ll-alive)%mod+mod)%mod;memset(h,0,sizeof h);if(alive!=1)//1-dead != 0{ll invd=qmi(dead,mod-2);h[0]=g[0]*invd%mod;for(int j=1;j<k;j++)h[j]=(g[j]-alive*h[j-1]%mod+mod)%mod*invd%mod;}else//dead=1{for(int j=0;j<=k;j++)h[j]=g[j+1];}for(int j=0;j<k;j++) ans=(ans+h[j]*inv[j+1]%mod)%mod;ans=ans*alive%mod;cout<<ans<<' ';}cout<<'\n'; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];inv[i]=qmi(i,mod-2);f[i][a[i]]=1;}cin>>m;while(m--){int op;cin>>op;if(op==0){int id;ll u,v;cin>>id>>u>>v;attack(id,1ll*u*qmi(v,mod-2)%mod);}else{int k;cin>>k;for(int i=1;i<=k;i++) cin>>b[i];solve(k);}}for(int i=1;i<=n;i++){ll ans=0;for(int j=1;j<=a[i];j++)ans=(ans+j*f[i][j]%mod)%mod;cout<<ans<<' ';}return 0; }

要加油哦~

總結

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

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