BZOJ5340: [Ctsc2018]假面-期望DP

传送门

题意：

有 2 个技能：

1.锁定：对一名指定的敌方单位使用，以 p 的概率对该单位造成 1 点伤害。

2.结界：在一片区域施放结界，让该区域内的所有其他单位无法动弹。

如果一个单位的生命值降至 0 或 0 以下，那么该单位就会死亡。

现在有 n 个敌方单位（编号从 1 至 n），编号为 i 的敌方单位有 mi 点生命值。

按顺序施放 Q 个技能：

1.对于锁定技能：针针会指定一个敌方单位 id，并对它施放。由于决定概率系数 p 的因素很多，因此每次的 p 都不一定相同。特别地，如果该敌方单位已经死亡，那么该技能不会造成任何效果。

2.对于结界技能：对 k 个指定的敌方单位施放，命中这k个单位中的恰好1个敌方单位。命中每个存活的敌方单位的概率是相等的（也就是说已经死亡的敌方单位不会有任何影响）。特别地，如果这 k 个敌方单位均已死亡，那么该技能同样不会命中任何敌方单位。

现在我们想知道：

1.对于施放的每个结界技能，它命中各敌人的概率分别是多少。

2.在所有技能施放完毕后，所有敌方单位剩余生命值的期望分别是多少。

请输出其在模 998, 244, 353 意义下的值。

设释放结界技能的次数为C

n≤200，Q≤200,000，C≤1000，mi≤100

Solution：

对于1技能，我们有一个简单的dp：设 f[i][j] 为第i个单位剩余j滴血的概率

转移即为 f[i][j]=f[i][j+1]∗p+f[i][j]∗(1−p)

需要对0进行特殊转移： f[i][0]=f[i][1]∗p+f[i][0]

对于2技能，我们可以对于每个单位进行枚举：对于每个单位i，dp[j]表示当i一定存活时，总共存活j个单位的概率，转移时枚举剩下的单位p， dp[j]=dp[j]∗f[p][0]+dp[j−1]∗(1−f[p][0]) 进行转移即可

最终的答案即为 ∑kp=1dp[p]p∗(1−f[i][0])

对于1技能，dp一次的复杂度为 O(m)

对于2技能，dp一次的复杂度为 O(n3)

总复杂度 O(n3C+mQ) ，瓶颈在2技能上，所以说我们考虑优化：

我们发现2技能内部的每一次dp，都需要重复转移许多次，那么这么重复转移是否是必要的呢？

其实dp数组是可以倒推的，假设前一次的状态为 dp′[i]

那么 dp[j]=dp′[j]∗f[p][0]+dp′[j−1]∗(1−f[p][0])

dp′[j]=dp′[j−1]∗(1−f[p][0])−dp[j]f[p][0]

我们知道dp[0]是恒等于0的（因为我们的dp是建立在某个单位一定存活的基础之上的）

所以上一次的dp数组可以通过当前的dp数组求出，那么我们只需要求一次最终的dp数组，对每个单位进行倒推即可，复杂度变为单次 O(n2)

注意需要预处理1~n的逆元，写代码的时候忘记了求逆元复杂度导致怎么卡常都卡不过QAQ，这就使得优化掉逆元后代码跑的飞快233

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,m,hp[210],q;
int f[210][110];
int dp[210],g[210],num,a[210]; 
int inv[210];
const int mod=998244353;
int fast_pow(int x,int a)
{
    int ans=1;
    for (;a;x=1ll*x*x%mod,a>>=1)
        if (a&1) ans=1ll*ans*x%mod;
    return ans; 
}
char c[14];
void print(int x)
{
    if (x==0) {putchar('0'),putchar(' ');return;} 
    int num=0;
    while (x) c[++num]=(x%10)+48,x/=10;
    while (num) putchar(c[num--]);
    putchar(' ');
}
void getdp()
{
    memset(dp,0,sizeof(dp));
    dp[1]=1;
    int top=1;
    for (int j=1;j<=num;j++)
    {
    //  if (i==j) continue;
        for (int k=top+1;k>=1;k--)
            dp[k]=(1ll*dp[k]*f[a[j]][0]+1ll*dp[k-1]*(1-f[a[j]][0]+mod))%mod;
        while (dp[top+1]) top++;
    }
    for (int i=1;i<=num;i++)
    {
        if (f[a[i]][0]==0)
        {
            for (int k=1;k<=top;k++) g[k]=dp[k+1];
        }
        else
        {
            int nw=fast_pow(f[a[i]][0],mod-2);
            for (int k=1;k<=top;k++)
                g[k]=1ll*(dp[k]+mod-1ll*g[k-1]*(1-f[a[i]][0]+mod)%mod)*nw%mod; 
        }
        int ans=0;
        for (int j=1;j<=min(num,top);j++)
            ans=(1ll*g[j]*inv[j]+ans)%mod;
        ans=1ll*ans*(1-f[a[i]][0]+mod)%mod;
        print(ans);

    }
    printf("\n");

}
int read()
{
    int x=0;
    char ch=getchar();
    while (ch>'9'||ch<'0') ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int main()
{
//  freopen("faceless6.in","r",stdin);
//  freopen("faceless6.out","w",stdout);
    n=read();
    for (int i=1;i<=n;i++) hp[i]=read(),f[i][hp[i]]=1;
    for (int i=1;i<=n;i++) inv[i]=fast_pow(i,mod-2);
    q=read();
    for (int op,id,u,v,i=1;i<=q;i++)
    {
        op=read();
        if (op==0)
        {
            id=read(),u=read(),v=read();
            int p=1ll*u*fast_pow(v,mod-2)%mod;
            f[id][0]=(1ll*f[id][1]*p+f[id][0])%mod;
            for (int j=1;j<=hp[id];j++)
                f[id][j]=(1ll*f[id][j+1]*p+1ll*f[id][j]*(1-p+mod))%mod;
        }
        else
        {
            num=read();for (int j=1;j<=num;j++) a[j]=read();
            getdp();
        }
    }
    for (int i=1;i<=n;i++)
    {
        int ans=0;
        for (int j=0;j<=hp[i];j++)
            ans=(1ll*j*f[i][j]+ans)%mod;
        print(ans);
    }
}