← 返回题目列表

Codeforces · 1172/C2

C2. Nauuo 和图片(硬版)

中文机器翻译题面 查看原题

简单版本和困难版本之间的唯一区别是限制。

Nauuo是一个喜欢随机图片网站的女孩。

有一天,她自己制作了一个随机图片网站,其中包含$$$n$$$图片。

当 Nauuo 访问该网站时,她只看到一张图片。该网站不会以相同的概率显示每张图片。第$$$i$$$张图片的权重为非负$$$w_i$$$,第$$$i$$$张图片被显示的概率为$$$\frac{w_i}{\sum_{j=1}^nw_j}$$$。也就是说,一张图片被展示的概率与其权重成正比。

然而,Nauuo 发现一些她不喜欢的图片显示得太频繁。

为了解决这个问题,她想出了一个好主意:当她看到自己喜欢的图片时,她会在其权重上加上$$$1$$$;否则,她会从它的重量中减去$$$1$$$。

Nauuo 将访问该网站 $$$m$$$ 次。她想知道在所有 $$$m$$$ 访问模 $$$998244353$$$ 后每张图片的预期权重。你能帮助她吗?

第$$$i$$$张图片的预期权重可以用$$$\frac {q_i} {p_i}$$$表示,其中$$$\gcd(p_i,q_i)=1$$$,你需要打印一个整数$$$r_i$$$,满足$$$0\le r_i<998244353$$$并且$$$r_i\cdot p_i\equiv q_i\pmod{998244353}$$$。可以证明这样的$$$r_i$$$存在并且是唯一的。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$1\le m\le 3000$$$) — 图片数量和网站访问次数。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$a_i$$$ 是 $$$0$$$ 或 $$$1$$$) — 如果 $$$a_i=0$$$ ,Nauuo 不喜欢第 $$$i$$$ 图片;否则 Nauuo 喜欢第 $$$i$$$ 张图片。保证至少有一张Nauuo喜欢的图片。

第三行包含 $$$n$$$ 正整数 $$$w_1,w_2,\ldots,w_n$$$ ($$$w_i \geq 1$$$) — 图片的初始权重。保证所有初始权重之和不超过$$$998244352-m$$$。

输出

输出包含 $$$n$$$ 整数 $$$r_1,r_2,\ldots,r_n$$$ — 预期权重以 $$$998244353$$$ 为模。

示例

输入 #1

2 1
0 1
2 1

输出 #1

332748119
332748119

输入 #2

1 2
1
1

输出 #2

3

输入 #3

3 3
0 1 1
4 3 5

输出 #3

160955686
185138929
974061117

注意

在第一个示例中,如果唯一一次访问以 $$$\frac 2 3$$$ 的概率显示第一张图片,则最终权重为 $$$(1,1)$$$;如果唯一一次访问以 $$$\frac1 3$$$ 的概率显示第二张图片,则最终权重为 $$$(2,2)$$$。

因此,两个预期权重均为 $$$\frac2 3\cdot 1+\frac 1 3\cdot 2=\frac4 3$$$ 。

因为 $$$332748119\cdot 3\equiv 4\pmod{998244353}$$$,您需要打印 $$$332748119$$$ 而不是 $$$\frac4 3$$$ 或 $$$1.3333333333$$$。

在第二个例子中,Nauuo 喜欢的图片只有一张,因此 Nauuo 每次访问网站时,$$$w_1$$$ 都会增加 $$$1$$$。

因此,预期重量为$$$1+2=3$$$。

Nauuo 非常调皮,所以她没有给你任何关于第三个例子的提示。