Nauuo and Pictures (hard version)

题意翻译

[**Easy version**](https://www.luogu.com.cn/problem/CF1172C1) 和 [**Hard version**](https://www.luogu.com.cn/problem/CF1172C2) 的唯一区别是数据范围。 一个随机图片网站上有 $n$ 张图片，每次访问这个网站时会显示一张图片。 但是每张图片显示的概率不一定相同。 每张图片有一个权值，设第 $i$ 张图片的权值为 $w_i$，则第 $i$ 张图片被显示的概率为 $\frac{w_i}{\sum_{j=1}^n w_j}$ 。 也就是说，一张图片被显示的概率与其权值成正比。 每张照片会被 "喜欢" 或 "不喜欢" ，用 $a$ 来表示。 若 $a_i=0$ ，则第 $i$ 张照片不被喜欢；若 $a_i=1$ ，则第 $i$ 张照片被喜欢。 每次访问网站时，若出现的照片被喜欢，则 $w_i$ 加一，否则 $w_i$ 减一。 接下来会访问该网站 $m$ 次，请求出每张图片在 $m$ 次访问后的预期权值 $\bmod 998244353$ 的结果 。 数据范围：$1\leqslant n \leqslant 2\times10^5$ ，$1\leqslant m\leqslant 3000$ ，$1\leqslant w_i$ 。

题目描述

The only difference between easy and hard versions is constraints. Nauuo is a girl who loves random picture websites. One day she made a random picture website by herself which includes $ n $ pictures. When Nauuo visits the website, she sees exactly one picture. The website does not display each picture with equal probability. The $ i $ -th picture has a non-negative weight $ w_i $ , and the probability of the $ i $ -th picture being displayed is $ \frac{w_i}{\sum_{j=1}^nw_j} $ . That is to say, the probability of a picture to be displayed is proportional to its weight. However, Nauuo discovered that some pictures she does not like were displayed too often. To solve this problem, she came up with a great idea: when she saw a picture she likes, she would add $ 1 $ to its weight; otherwise, she would subtract $ 1 $ from its weight. Nauuo will visit the website $ m $ times. She wants to know the expected weight of each picture after all the $ m $ visits modulo $ 998244353 $ . Can you help her? The expected weight of the $ i $ -th picture can be denoted by $ \frac {q_i} {p_i} $ where $ \gcd(p_i,q_i)=1 $ , you need to print an integer $ r_i $ satisfying $ 0\le r_i<998244353 $ and $ r_i\cdot p_i\equiv q_i\pmod{998244353} $ . It can be proved that such $ r_i $ exists and is unique.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1\le n\le 2\cdot 10^5 $ , $ 1\le m\le 3000 $ ) — the number of pictures and the number of visits to the website. The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ a_i $ is either $ 0 $ or $ 1 $ ) — if $ a_i=0 $ , Nauuo does not like the $ i $ -th picture; otherwise Nauuo likes the $ i $ -th picture. It is guaranteed that there is at least one picture which Nauuo likes. The third line contains $ n $ positive integers $ w_1,w_2,\ldots,w_n $ ( $ w_i \geq 1 $ ) — the initial weights of the pictures. It is guaranteed that the sum of all the initial weights does not exceed $ 998244352-m $ .

输出格式

The output contains $ n $ integers $ r_1,r_2,\ldots,r_n $ — the expected weights modulo $ 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

说明

In the first example, if the only visit shows the first picture with a probability of $ \frac 2 3 $ , the final weights are $ (1,1) $ ; if the only visit shows the second picture with a probability of $ \frac1 3 $ , the final weights are $ (2,2) $ . So, both expected weights are $ \frac2 3\cdot 1+\frac 1 3\cdot 2=\frac4 3 $ . Because $ 332748119\cdot 3\equiv 4\pmod{998244353} $ , you need to print $ 332748119 $ instead of $ \frac4 3 $ or $ 1.3333333333 $ . In the second example, there is only one picture which Nauuo likes, so every time Nauuo visits the website, $ w_1 $ will be increased by $ 1 $ . So, the expected weight is $ 1+2=3 $ . Nauuo is very naughty so she didn't give you any hint of the third example.

题意翻译

[**Easy version**](https://www.luogu.com.cn/problem/CF1172C1) 和 [**Hard version**](https://www.luogu.com.cn/problem/CF1172C2) 的唯一区别是数据范围。 一个随机图片网站上有 $n$ 张图片，每次访问这个网站时会显示一张图片。 但是每张图片显示的概率不一定相同。 每张图片有一个权值，设第 $i$ 张图片的权值为 $w_i$，则第 $i$ 张图片被显示的概率为 $\frac{w_i}{\sum_{j=1}^n w_j}$ 。 也就是说，一张图片被显示的概率与其权值成正比。 每张照片会被 "喜欢" 或 "不喜欢" ，用 $a$ 来表示。 若 $a_i=0$ ，则第 $i$ 张照片不被喜欢；若 $a_i=1$ ，则第 $i$ 张照片被喜欢。 每次访问网站时，若出现的照片被喜欢，则 $w_i$ 加一，否则 $w_i$ 减一。 接下来会访问该网站 $m$ 次，请求出每张图片在 $m$ 次访问后的预期权值 $\bmod 998244353$ 的结果 。 数据范围：$1\leqslant n \leqslant 2\times10^5$ ，$1\leqslant m\leqslant 3000$ ，$1\leqslant w_i$ 。