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

## Sol

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

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
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);
for(int i = 1; i <= N; i++) a[i] = read(), t[0][i][a[i]] = 1, f[0][i] = a[i];
int o = 1;
for(int i = 1; i <= Q; i++, o ^= 1) {
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;
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
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) {
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);
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);
int o = 1;
for(int i = 1; i <= Q; i++, o ^= 1) {
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;
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) {
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 条评论

• ### ZR国庆Round2解题报告

然后刚T3暴力，刚完还有2h左右。。然后，，这时候我zz的选择去打T2的暴力，然而T2暴力真的不是一般的难写。。

• ### 洛谷P3809 【模板】后缀排序

题目背景 这是一道模板题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输...

• ### 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列，显然这个序列要满足最后一个$$\mid 1$$要在$$\& 0$$之后

• ### 第88场周赛

第二反应：根据上述这个模拟超时过程，想一优化，shifts数组后面开始，逐个偏移，根据描述，后面的偏移会加到前面。于是有了后缀和这一说法。

• ### 【计算机本科补全计划】CCF计算机职业资格认证 2016-09 试题详解

正文之前 我要东山再起了！！没错CCF迫在眉睫（其实是我以为报名之后一个月才考，结果报名截止之后一周就考试！(╯‵□′)╯︵┻━┻！！！还能好好做朋友吗！！）所...

• ### HDU 2196 Computer(树的直径)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2196

• ### HDU 2503 a/b + c/d(最大公约数与最小公倍数,板子题)

话不多说，日常一水题，水水更健康！┗|｀O′|┛ 嗷~~ a/b + c/d Time Limit: 1000/1000 MS (Java/Others)   ...

• ### ZR国庆Round2解题报告

然后刚T3暴力，刚完还有2h左右。。然后，，这时候我zz的选择去打T2的暴力，然而T2暴力真的不是一般的难写。。

• ### LeetCode31|打印从1到最大的n位数

这道题算是api的使用方式了，数据的计算，其实自己也没有什么好说的了，但是由于文章的字数必需要达到300字，所有有些时候就只好在这里唠会嗑了，因为文章的原创对于...

• ### 牛客小白月赛11D（分治、RMQ）

定义一个玄学节点叫做 R，每次操作读入 val ，执行 Insert(R,val)。