LOJ#2552. 「CTSC2018」假面(期望 背包)

题意

题目链接

Sol

多年以后,我终于把这题的暴力打出来了qwq 好感动啊。。

刚开始的时候想的是:

设\(f[i][j]\)表示第\(i\)轮, 第\(j\)个人血量的期望值

转移的时候若要淦这个人,那么\(f[i][j] = (f[i - 1][j] + 1) * p + (f[i - 1][j]) * (1 - p)\)

然后发现自己傻逼了。。因为期望不能正着推。

考虑直接推概率,设\(t[k][i][j]\)表示第\(k\)轮,第\(i\)个人,血量为\(j\)的概率

这玩意儿是可以转移的,就是判一下这次打中了没有

第二问可以对每个点分别算答案,设\(g[i][j]\)表示除必须活着的人外,前\(i\)个人中,有\(j\)个活着的概率,背包转移一下

这样复杂度是\(O(qn + n^3)\)的

显然第二问看起来非常暴力,

标算的做法好像叫“退背包”,也就是从背包中删除一个元素

先不考虑某个元素必须存活,推一遍得到\(g[i][j]\)表示前\(i\)个人中,有\(j\)个存活的概率

考虑转移的式子,设\(ali[i]\)表示第\(i\)个人活着的概率

\(g[i][j] = g[i - 1][j - 1] * ali[i] + g[i - 1][j] * (1 - ali[i])\)

而我们要得到的实际上就是\(g[i-1][j]\)这一项

那么\(g[i - 1][j] = \frac{g[i][j] - g[i - 1][j - 1] * ali[i]}{1 - ali[i]}\)

倒着推一遍即可,注意当\(1 - ali[i] = 0\)的时候需要特判,此时\(g[i - 1][j] = g[i][j + 1]\)

70分

#include<bits/stdc++.h>
//#define int long long 
using namespace std;
const int MAXN = 201, mod = 998244353;
int f[2][MAXN], g[MAXN][MAXN], t[2][MAXN][MAXN];
// f: expect 
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, a[MAXN], Q, em[MAXN];
int fp(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = 1ll * base * a % mod;
        a = 1ll * a * a % mod; p >>= 1;
    }
    return base;
}
int inv(int a) {
    return fp(a, mod - 2);
}
int add(int x, int y) {
    if(x + y < 0) return x + y + mod;
    else return x + y >= mod ? x + y - mod : x + y;
}
int mul(int x, int y) {
    x = (x + mod) % mod; y = (y + mod) % mod;
    return 1ll * x * y % mod;
}
int solve(int id, int o, int N) {//这里dp的时候不能直接表示有j个活着,必须表示除i之外有j个活着。。 
    memset(g, 0, sizeof(g));
    g[0][0] = 1; 
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j <= N; j++) {
            if(em[i] ^ id) {
                g[i][j] = mul(g[i - 1][j], t[o][em[i]][0]);
                if(j) g[i][j] = add(g[i][j], mul(g[i - 1][j - 1], 1 - t[o][em[i]][0]));
            }
            else g[i][j] = g[i - 1][j];
        }
    }
    int ans = 0;
    for(int i = 0; i < N; i++) 
        ans = add(ans, mul(mul(1 - t[o][id][0], g[N][i]), inv(i + 1)));
    return ans;
}
signed main() {
//  freopen("a.in", "r", stdin);
//  freopen("b.out", "w", stdout);
    N = read();
    for(int i = 1; i <= N; i++) a[i] = read(), t[0][i][a[i]] = 1, f[0][i] = a[i];
    Q = read();
    int o = 1;
    for(int i = 1; i <= Q; i++, o ^= 1) {
        int opt = read();
        memcpy(t[o], t[o ^ 1], sizeof(t[o]));
        if(opt == 0) {//
            int id = read(), u = read(), v = read(), p = 1ll * u * inv(v) % mod;
            t[o][id][0] = add(t[o][id][0], mul(p, t[o][id][1]));
            for(int j = 1; j <= a[id]; j++) t[o][id][j] = add(mul(p, t[o ^ 1][id][j + 1]), mul(1 - p, t[o ^ 1][id][j]));
        } else if(opt == 1) {
            int k = read(), cnt = 0;
            for(int i = 1; i <= k; i++) em[++cnt] = read();
            for(int i = 1; i <= k; i++) printf("%d ", solve(em[i], o, cnt)); puts("");
        }
    }
    for(int i = 1; i <= N; i++) {
        int ans = 0;
        for(int j = 1; j <= a[i]; j++) 
            ans = add(ans, mul(j, t[o ^ 1][i][j]));
        printf("%d ", ans);
        
    }
    return 0;
}
/*
*/

100分

#include<bits/stdc++.h>
//#define int long long 
using namespace std;
const int MAXN = 201, mod = 998244353;
int f[2][MAXN], g[MAXN][MAXN], t[2][MAXN][MAXN];
// f: expect 
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, a[MAXN], Q, em[MAXN], ans[MAXN], ali[MAXN], tp[MAXN], Inv[MAXN];
int add(int x, int y) {
    if(x + y < 0) return x + y + mod;
    else return x + y >= mod ? x + y - mod : x + y;
}
int mul(int x, int y) {
    x = (x + mod) % mod; y = (y + mod) % mod;
    return 1ll * x * y % mod;
}
int fp(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = 1ll * base * a % mod;
        a = 1ll * a * a % mod; p >>= 1;
    }
    return base;
}
int inv(int a) {
    a = add(a, mod);
    return fp(a, mod - 2);
}

void Pre(int o, int N) {
//  memset(g, 0, sizeof(g));
    g[0][0] = 1; 
    for(int i = 1; i <= N; i++) {
        ali[i] = (1 - t[o][em[i]][0] + mod) % mod;//alive
        for(int j = 0; j <= i; j++) {
            g[i][j] = mul(g[i - 1][j], t[o][em[i]][0]);
            if(j) g[i][j] = add(g[i][j], mul(g[i - 1][j - 1], ali[i]));
        }
    }   
}
int solve(int id, int o, int N) {
    //memset(tp, 0, sizeof(tp));
    if(!ali[id]) return 0;
    if(ali[id] == 1) {
        for(int i = 1; i <= N; i++) tp[i - 1] = g[N][i];
    } else {
        int down = inv(1 - ali[id]);
        tp[0] = mul(g[N][0], down);
        for(int i = 1; i <= N; i++) 
            tp[i] = mul(g[N][i] - mul(tp[i - 1], ali[id]), down);
    }

    int ans = 0;
    for(int i = 1; i <= N; i++) 
        ans = add(ans, mul(mul(ali[id], tp[i - 1]), Inv[i]));
    return ans;
}
signed main() {
    //freopen("faceless10.in", "r", stdin);
//  freopen("b.out", "w", stdout);
    N = read();
    for(int i = 1; i <= N; i++) a[i] = read(), t[0][i][a[i]] = 1, f[0][i] = a[i], Inv[i] = inv(i);
    Q = read();
    int o = 1;
    for(int i = 1; i <= Q; i++, o ^= 1) {
        int opt = read();
        memcpy(t[o], t[o ^ 1], sizeof(t[o]));
        if(opt == 0) {//
            int id = read(), u = read(), v = read(), p = 1ll * u * inv(v) % mod;
            t[o][id][0] = add(t[o][id][0], mul(p, t[o][id][1]));
            for(int j = 1; j <= a[id]; j++) t[o][id][j] = add(mul(p, t[o ^ 1][id][j + 1]), mul(1 - p, t[o ^ 1][id][j]));
        } else if(opt == 1) {
            int k = read();
            for(int i = 1; i <= k; i++) em[i] = read();
            Pre(o, k);
            for(int i = k; i >= 1; i--) ans[i] = solve(i, o, k);
            for(int i = 1; i <= k; i++) printf("%d ", ans[i]); puts("");
        }
    }
    for(int i = 1; i <= N; i++) {
        int ans = 0;
        for(int j = 1; j <= a[i]; j++) 
            ans = add(ans, mul(j, t[o ^ 1][i][j]));
        printf("%d ", ans);
        
    }
    return 0;
}
/*
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ1468: Tree

Description 给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K Input N(n<=40000) 接下来n-1行边描...

32690
来自专栏数据结构与算法

2017.5.13阶段模拟考试

预计分数:100+50(其实感觉自己写的对)+100 实际分数:100+0+100 P1149 火柴棒等式 题目描述 给你n根火柴棍,你可以拼出多少个形如“A+...

35660
来自专栏数据结构与算法

各种数论模板 不断更新 绝对精品

1.筛法求素数 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #inclu...

35190
来自专栏数据结构与算法

BZOJ3398: [Usaco2009 Feb]Bullcow 牡牛和牝牛(dp)

设$f[i]$表示到第$i$个位置,该位置放了牡牛的方案,$g[i]$表示到第$i$个位置,且该位置放了牝牛的方案数

7810
来自专栏数据结构与算法

11.6NOIP模拟赛解题报告

很显然的一个贪心是从左往右扫,如果遇到一个不合法的点\(i\),那么升级\(i + R\)处的炮台。。

10030
来自专栏calmound

HDU 4609 3-idiots

http://acm.hdu.edu.cn/showproblem.php?pid=4609 题意:给你一组数,问可以组成多少个三角形 分析:才知道原来有FFT...

29460
来自专栏owent

PKU POJ 2728 Desert King 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2728

8830
来自专栏数据结构与算法

Day4上午解题报告

预计分数:50 +0+0=50 实际分数:50+0+10=60 毒瘤出题人,T3不给暴力分 (*  ̄︿ ̄)  T1 https://www.luogu.org/...

28140
来自专栏数据结构与算法

BZOJ1576: [Usaco2009 Jan]安全路经Travel(最短路 并查集)

给你一张无向图,保证从1号点到每个点的最短路唯一。对于每个点求出删掉号点到它的最短路上的最后一条边(就是这条路径上与他自己相连的那条边)后1号点到它的最短路的长...

8110
来自专栏数据结构与算法

codeforces1025

首先考虑一个很显然的区间dp, $f[l][r][root]$表示$(l, r)$区间内,以$root$为根是否可行

6710

扫码关注云+社区

领取腾讯云代金券