网站开发程序员招聘,应届生简历模板,17年哪个网站做h5最好,wordpress 判断是否为首页P4564 [CTSC2018]假面
首先容易看出结界技能对第二问敌方剩余生命值期望没有影响。
如何求出第iii个人的剩余生命值期望#xff1f; 只需要根据Ei∑j0aijfi,jE_i\sum_{j0}^{a_i}jf_{i,j}Ei∑j0aijfi,j 预处理fi,jf_{i,j}fi,j#xff1a;第iii个人的剩余生命值为j…P4564 [CTSC2018]假面
首先容易看出结界技能对第二问敌方剩余生命值期望没有影响。
如何求出第iii个人的剩余生命值期望 只需要根据Ei∑j0aij×fi,jE_i\sum_{j0}^{a_i}j×f_{i,j}Ei∑j0aij×fi,j 预处理fi,jf_{i,j}fi,j第iii个人的剩余生命值为jjj的期望aia_iai表示最初生命值
由于每次锁定技能只能明确对一名地方单位造成攻击ppp概率击中而qqq概率不中每次只需要O(ai)O(a_i)O(ai)的代价维护fi,jf_{i,j}fi,j总的时间复杂度O(Qm)O(Qm)O(Qm) 转移方程fi,jpfi,j1qfi,jf_{i,j}pf_{i,j1}qf_{i,j}fi,jpfi,j1qfi,j注意fi,0pfi,1fi,0f_{i,0}pf_{i,1}f_{i,0}fi,0pfi,1fi,0 对于第二个技能想要知道命中uuu的概率我们需要知道除了u之外还有jjj个人存活下不妨叫做gu,jg_{u,j}gu,j。
只需要把除了uuu的其他敌人vvv拿出来跑一遍背包即可注意逆序 gu,jalivev×gu,j−1deadv×gu,jg_{u,j}\text{alive}_v×g_{u,j-1}\text{dead}_v×g_{u,j}gu,jalivev×gu,j−1deadv×gu,j
显然alivev1−fv,0\text{alive}_v1-f_{v,0}alivev1−fv,0v存活下来的概率deadvfv,0\text{dead}_vf_{v,0}deadvfv,0死了的概率。
对于第二个技能范围的每个敌人我们都需要预处理一下gu,jg_{u,j}gu,j数组也就是O(n3)O(n^3)O(n3)的复杂度第二个技能总时间复杂度O(Cn3)O(Cn^3)O(Cn3)代码如下这时候我们能够拿到707070ptsO(QmCn3)O(QmCn^3)O(QmCn3)
#includecstring
#includeiostream
using namespace std;
using lllong long;
constexpr ll mod998244353;
ll qmi(ll a,ll b)
{ll res1;while(b){if(b1) resres*a%mod;aa*a%mod;b1;}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-pmod)%mod;for(int j0;ja[i];j){if(j)f[i][j](p*f[i][j1]%modq*f[i][j]%mod)%mod;elsef[i][j](p*f[i][j1]%modf[i][j])%mod;}
}
void solve(int k)//O(n^3)
{for(int u1;uk;u)//枚举范围呢的每一个敌人{memset(g,0,sizeof g);g[0]1ll;for(int i1;ik;i)//除了u的敌人跑一边背包{if(ui) continue;ll alive((1ll-f[b[i]][0])%modmod)%mod;ll dead((1ll-alive)%modmod)%mod;for(int ji;j0;j--)//逆序{if(j) g[j](g[j]*deadg[j-1]*alive%mod)%mod;else g[j]g[j]*dead%mod;}}ll ans0;for(int j0;jk;j) ans(ansg[j]*inv[j1]%mod)%mod;ansans*((1ll-f[b[u]][0])%modmod)%mod;coutans ;}cout\n;
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinn;for(int i1;in;i){cina[i];inv[i]qmi(i,mod-2);f[i][a[i]]1;}cinm;while(m--){int op;cinop;if(op0){int id;ll u,v;ciniduv;attack(id,1ll*u*qmi(v,mod-2)%mod);}else{int k;cink;for(int i1;ik;i) cinb[i];solve(k);}}for(int i1;in;i){ll ans0;for(int j1;ja[i];j)ans(ansj*f[i][j]%mod)%mod;coutans ;}return 0;
}考虑优化显然我们TLE是由于第二个操作如果每次枚举然后跑背包似乎有些冗余。我们另设gjg_jgj表示jjj个人或者的概率而用hu,jh_{u,j}hu,j表示除了u之外还有jjj个人存活下也就是上面的gu,jg_{u,j}gu,j有下面递推 gjaliveu×hu,j−1deadu×hu,jg_j\text{alive}_u×h_{u,j-1}\text{dead}_u×h_{u,j}gjaliveu×hu,j−1deadu×hu,j 于是有hu,jgj−aliveu×hu,j−1deaduh_{u,j}\frac{g_j-\text{alive}_u×h_{u,j-1}}{\text{dead}_u}hu,jdeadugj−aliveu×hu,j−1 于是我们只需要O(n2)O(n^2)O(n2)预处理gjg_jgj然后枚举uuu线性求出hu,jh_{u,j}hu,j同样时间复杂度O(n2)O(n^2)O(n2)那么技能二时间复杂度O(Cn2)O(Cn^2)O(Cn2)
注意gjaliveu×hu,j−1,deadu0g_j\text{alive}_u×h_{u,j-1},\text{dead}_u0gjaliveu×hu,j−1,deadu0 即存在hu,jgj1h_{u,j}g_{j1}hu,jgj1
总时间复杂度O(QmCn2)O(QmCn^2)O(QmCn2)
#includecstring
#includeiostream
using namespace std;
using lllong long;
constexpr ll mod998244353;
ll qmi(ll a,ll b)
{ll res1;while(b){if(b1) resres*a%mod;aa*a%mod;b1;}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-pmod)%mod;for(int j0;ja[i];j){if(j)f[i][j](p*f[i][j1]%modq*f[i][j]%mod)%mod;elsef[i][j](p*f[i][j1]%modf[i][j])%mod;}
}
void solve(int k)
{memset(g,0,sizeof g);g[0]1ll;for(int i1;ik;i)//预处理 g{ll alive((1ll-f[b[i]][0])%modmod)%mod;ll dead((1ll-alive)%modmod)%mod;for(int ji;j0;j--){if(j) g[j](g[j]*deadg[j-1]*alive%mod)%mod;else g[j]g[j]*dead%mod;}}for(int u1;uk;u){ll ans0;ll alive((1ll-f[b[u]][0])%modmod)%mod;ll dead((1ll-alive)%modmod)%mod;memset(h,0,sizeof h);if(alive!1)//1-dead ! 0{ll invdqmi(dead,mod-2);h[0]g[0]*invd%mod;for(int j1;jk;j)h[j](g[j]-alive*h[j-1]%modmod)%mod*invd%mod;}else//dead1{for(int j0;jk;j)h[j]g[j1];}for(int j0;jk;j) ans(ansh[j]*inv[j1]%mod)%mod;ansans*alive%mod;coutans ;}cout\n;
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinn;for(int i1;in;i){cina[i];inv[i]qmi(i,mod-2);f[i][a[i]]1;}cinm;while(m--){int op;cinop;if(op0){int id;ll u,v;ciniduv;attack(id,1ll*u*qmi(v,mod-2)%mod);}else{int k;cink;for(int i1;ik;i) cinb[i];solve(k);}}for(int i1;in;i){ll ans0;for(int j1;ja[i];j)ans(ansj*f[i][j]%mod)%mod;coutans ;}return 0;
}要加油哦~
