开家网站设计公司,哪个婚纱摄影,上海公上海公司网站建设,电商运营培训机构排名URL#xff1a;https://atcoder.jp/contests/abc295 目录
E
Problem/题意
Thought/思路
Code/代码 E
Problem/题意
给定长度为 N 的数组 A。进行如下操作#xff1a;
若 Ai 0#xff0c;将 Ai 等概率地变为 1 ~ M 中的任意一个数#xff1b;对 A 排序#xff1b; …URLhttps://atcoder.jp/contests/abc295 目录
E
Problem/题意
Thought/思路
Code/代码 E
Problem/题意
给定长度为 N 的数组 A。进行如下操作
若 Ai 0将 Ai 等概率地变为 1 ~ M 中的任意一个数对 A 排序
问第 K 个数地期望是多少。
Thought/思路
概率 DP。一开始想不明白这个公式概率论白雪了
设我们要求的 A[k] x 且 P[i] 为 x i 的概率那么就有如下公式 关于这条公式地推导https://zhuanlan.zhihu.com/p/617048570 因此接下来的问题就变成了对于每个 i求出 P(A[k] i)。 但是我们不知道 A[k] 该怎么取值所以还需要将 P(A[k] i) 转换为后面 N - K 1 个数 i 的概率也就是 [K, N] 中的数都 i 的概率。假设已经排好序
显然 [K, N] 中的数不会都 i而一般的情况就是[K, N] 中的前一部分的数 i、后一部分的数 i。 对于前一部分我们需要依靠 0 来变成 i 的数去替换他们所以记录前一部分的数的个数为 need这代表了所需要的 0 的最少数量。
也就是说如果 0 的数量设为 zerozero need那么就永远不可能满足 [K, N] 中的数都 i概率为 0反之如果 need 0就一定满足 [K, N] 中的数都 i概率为 1 基于概率为 0 的那种情况就一定能保证 need zero。
而 need 是需要的 0 的最少数量那么我们就可以设有 need 个 0 变成了 i 的数其带来的概率为 其中 P (m - i 1) / m意思是取出 i 的数的概率。
显然一共有 zero 个 0 可以使用所以考虑 [need, zero] 每一种情况即可。
Code/代码
#include bits/stdc.h#define int long longconst int mod 998244353;int n, m, k, a[2007], fact[2007], invf[2007];int ksm(int a, int b) {int res 1;while (b 0) {if (b 1) res res * a % mod;a a * a % mod;b / 2;}return res;
}void init() {fact[0] 1, invf[0] ksm(1, mod - 2);for (int i 1; i 2000; i) {fact[i] fact[i - 1] * i % mod;invf[i] ksm(fact[i], mod - 2) % mod;}
}int C(int x, int y) {if (x y) return 0;return fact[x] * invf[y] % mod * invf[x - y] % mod;
}signed main() {std::cin n m k;for (int i 1; i n; i) std::cin a[i];init();int ans 0;for (int i 1; i m; i) {int zero 0, need n - k 1;for (int j 1; j n; j) {if (a[j] i) need --;if (a[j] 0) zero ;}if (need 0 or need zero) { // [k, n] 都 i概率为 1[k, n] 小于 i 的个数0 补不上概率为 0。ans (ans (need 0 ? 1 : 0)) % mod;continue;}int p1 (m - i 1) * ksm(m, mod - 2) % mod; // 选出的数 i 的概率 p(m - i 1) / mint p2 (i - 1) * ksm(m, mod - 2) % mod; // 1 - p(i - 1) / mstd::vector int dp1(zero 1), dp2(zero 1);dp1[0] dp2[0] ksm(1, mod - 2);for (int j 1; j zero; j) {dp1[j] dp1[j - 1] * p1 % mod;dp2[j] dp2[j - 1] * p2 % mod;}// 用 0 补充 i 的数for (int j need; j zero; j) {ans (ans C(zero, j) * dp1[j] % mod * dp2[zero - j] % mod) % mod;}}std::cout ans;return 0;
}
