#2387. 开关
开关
开关
题目描述
1 开关 1.1 题目ᦣ䗄 九条可怜是一个贪玩的女孩子。 这天,她和她的好朋友法海哥哥去玩密室逃脱。在他们面前的是n 个开关,开始每个开关 都是关闭的状态。要通过这关,必须要让开关达到指定的状态。目标状态由一个长度为n 的01 数组s 给出,si = 0 表示第i 个开关在最后需要是关着的,si = 1 表示第i 个开关在最后需要 被打开。 然而作为闯关者,可怜和法海并不知道s。因此他们决定采用一个比较稳妥的方法:瞎按。 他们根据开关的外形、位置,通过一些玄学的方法给每一个开关赋予了一个权值pi(pi > 0)。每 一次,他们会以正比于pi 的概率(第i 个开关被选中的概率是 pi ∑n j=1 pj )选择并按下一个开关。 开关被按下后,状态会被反转,即开变关,关变开。注意,每一䕂的选择都是ᅠ全⣀ゟ的。 在按开关的过程中,一旦当前开关的状态达到了s,那么可怜和法海面前的门就会打开,他 们会马上停止按开关的过程并前往下一关。作为一名欧皇,可怜在按了∑n i=1 si 次后,就打开 了大门。为了感受一下自己的运气是多么的好,可怜想要让你帮她计算一下,用这种随机按的 方式,期望需要按多少次开关才能通过这一关。 1.2 输入格式 第一行输入一个整数n,表示开关的数量。 第二行输入n 个整数si(si ∈{0, 1}),表示开关的目标状态。第三行同样输入n 个整数pi, 表示每个开关的权值。 1.3 输出格式 输出一行一个整数,表示答案对998244353 取模后的值。即如果答案的最简分数表示为 x y(x ≥0, y ≥1, gcd(x, y) = 1),你需要输出x × y−1 mod 998244353。 1.4 样例输入1 2 1 1 1 1 1.5 样例输出1 4 2
1.6 样例㾷䞞 前两次按开关,有1 2 的概率达到s,有1 2 的概率回到原状。因此期望的按开关数量为: +∞ ∑ i=1 2i × (1 2 )i = 4 1.7 样例输入2 8 1 1 0 0 1 1 0 0 1 2 3 4 5 6 7 8 1.8 样例输出2 858924815 1.9 数据㣗ೈϢ约定 测试点 n 其他约定 测试点 n 其他约定 1 =2 无 6 ≤100 pi ≤2, si = 1 2 7 3 ≤8 8 ∑pi ≤2000 4 9 5 ≤100 pi = 1 10 无 对于100% 的数据,保证n ≥1, ∑n i=1 pi ≤5 × 104, pi ≥1。 3
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2
1 1
1 1
4
样例 2
8
1 1 0 0 1 1 0 0
1 2 3 4 5 6 7 8
858924815