Fork me on GitHub

「CTSC2018」假面(faceless) 概率与期望dp 递推 01背包还原

发表于 | 分类于
字数统计: 1,202字 | 阅读时长 ≈ 6分钟

Links there:CTSC2018假面

题意

有 $N$ 个敌人,每个敌人的血条为 $hp_i$ ,针针会丢 $Q$ 个技能.

技能1:指定一个敌方单位 $id$ ,给出 $u,v$ ,表示有 $\frac{u}{v}$ 的概率命中这个单位并造成1的伤害.

技能2:给出一个敌人的集合 ${ id_i }$ ,大小为 $k$ ,求每一个 $id_i$ 的存活期望.

最后还要求出每个敌人的血量剩余的期望.

(语文水平低下还恳请看原题面)

思路

考虑用 $a[i][j]$ 表示第 $i$ 个敌人剩下 $j$ 的血量的期望.

我们对于每一次技能 $1$ 是可以在 $O(hp[id])$ 内维护出这个 $a[id][j]$ 的,不难理解.

具体如下

$a[id][0] = a[id][0] + a[id][1] * p$ (已经挂了加上只剩下1滴血的这次挂掉的)

$a[id][i] = (a[id][i] (1-p) + a[id][i+1] p)$ (打得到与打不到)

用 $f[i][j]$ 表示前 $i$ 个敌人有 $j$ 个存活的期望.

用 $exist[i]$ 表示技能2中集合第 $i$ 个的存活期望

用 $dead[i]$ 表示技能2中集合第 $i$ 个的死亡期望

那么对于每一个技能 $2$ 本质上是一次询问操作.

通过考虑第 $i$ 个敌人的存活与否 不难有以下的转移

这样的话我们可以对于每一个集合中的元素 都这么暴力跑一遍就可以得到每个的期望.

时间复杂度为 $O(Cn^3 + Qm)$ , $m$ 为最大$hp$值.

只拿到 $70pts$

考虑优化 每一次我们都暴力重新转移 显然很多状态都被浪费了

考虑逆转移

令$f[i][j] = f’[j]$ 表示要转移到的状态. $f’[j]$ 由 $f[j-1],f[j]$ 转移而来

把它改写过来就是

这样每次我们就可以不需要暴力重置状态啦！这样就可以优化成$O(Cn^2+Qm)$

坑点 注意求逆元不要每次都在做的时候getinv(x,Mod)这样复杂度多了一个log(Mod)

虽然过了题但是还是要小心啊 预处理线推逆元.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}
const int Mod = 998244353;
const int MAXN = 210;
int n,hp[MAXN],f[MAXN][MAXN],g[MAXN],t[MAXN],Inv[MAXN],
    inv[MAXN],m,exist[MAXN],a[MAXN][MAXN],dead[MAXN],
    ans[MAXN];

///------------------head------------------
signed main(signed argc, char *argv[]){
    n=read();
    Inv[1] = 1;
    for (int i = 2; i <= 200; ++i) Inv[i] = (Mod - Mod/i) * (Inv[Mod % i]) % Mod;
    for (int i = 1; i <= n; ++i) hp[i] = read(),a[i][hp[i]] = 1;
    m=read();
    for (int op = 1; op <= m; ++op){
        int opt = read();
        if (opt) {
            int k = read();
            rep(i,1,k) t[i] = read();
            rep(i,1,k) exist[i] = (1-a[t[i]][0]+Mod) % Mod;
            rep(i,1,k) dead[i] = (1-exist[i]+Mod) % Mod;
            f[0][0] = 1;
            rep(i,1,n)
            {
                f[i][0] = f[i-1][0] * dead[i] % Mod;
                rep(j,1,i)
                f[i][j] = (f[i-1][j-1] * exist[i] % Mod + f[i-1][j] * dead[i] % Mod) % Mod;
            }
            rep(i,1,k) ans[i] = 0;
            rep(i,1,k) {
                if (exist[i]) {
                    if (exist[i] == 1) {
                        for (int j = 1; j <= k; ++j)
                        g[j-1] = f[k][j];
                    }
                    else {
                        int ded = getinv(dead[i],Mod);
                        g[0] = f[k][0] * ded % Mod;
                        for (int j = 1; j <= k; ++j)
                        g[j] = (f[k][j] - exist[i] * g[j-1] % Mod + Mod) * ded % Mod;
                    }
                    for (int j = 1; j <= k; ++j)
                    ans[i] = (ans[i] + exist[i] * g[j-1] % Mod * Inv[j] % Mod) % Mod;
                }
            }
            for (int i = 1; i <= k; ++i) printf("%lld ",ans[i]);
            puts("");
        }
        else{
            int id = read(),u = read(),v = read(),p = u * getinv(v,Mod) % Mod;
            a[id][0] = (a[id][0] + a[id][1] * p % Mod) % Mod;
            for (int i = 1; i <= hp[id]; ++i)
            a[id][i] = (a[id][i] * (1-p+Mod) % Mod + a[id][i+1] * p % Mod) % Mod;
        }
     }
     for (int i = 1; i <= n; ++i) ans[i] = 0;
     for (int i = 1; i <= n; ++i)
         for (int j = 1; j <= hp[i]; ++j)
         ans[i] = (ans[i] + a[i][j] * j % Mod) % Mod;
     for (int i = 1; i <= n; ++i) printf("%lld ",ans[i]);
    return 0;
}

/* Examples: */
/*
3
1 2 3
6
0 2 1 1
1 1 2
0 2 1 1
0 3 1 1
1 1 2
1 3 1 2 3
*/

/*
1
0
499122177 0 499122177
1 0 2
*/