AT_abc310_g [ABC310G] Takahashi And Pass-The-Ball Game

题目描述

有 $N$ 个高桥君。

第 $i$ 个高桥君拥有整数 $A_i$ 和 $B_i$ 个球。

高桥君们会从 $1$ 到 $K$ 之间均匀随机选择一个整数 $x$，然后重复以下操作 $x$ 次：

• 对于所有的 $i$，第 $i$ 个高桥君会把他手中的所有球全部交给第 $A_i$ 个高桥君。

请注意，操作是由所有 $N$ 个人同时进行的。

对于 $i=1,2,\ldots,N$，请你求出一系列操作结束后第 $i$ 个高桥君手中球的期望个数，并对 $998244353$ 取模。

期望值 $\bmod{998244353}$ 的定义
本题要求的期望值一定是有理数。在本题的约束下，设期望值为最简分数 $\frac{y}{x}$，保证 $x$ 不能被 $998244353$ 整除。此时，存在唯一的 $0\leq z<998244353$ 满足 $y\equiv xz\pmod{998244353}$，请输出 $z$。

输入格式

输入按以下格式从标准输入给出。

$N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$

输出格式

请输出 $i=1,2,\ldots,N$ 时操作结束后第 $i$ 个高桥君手中球的期望个数，对 $998244353$ 取模，空格分隔输出一行。

输入输出样例 #1

输入 #1

5 2
3 1 4 1 5
1 1 2 3 5

输出 #1

3 0 499122179 499122178 5

输入输出样例 #2

输入 #2

3 1000
1 1 1
1 10 100

输出 #2

111 0 0

输入输出样例 #3

输入 #3

16 1000007
16 12 6 12 1 8 14 14 5 7 6 5 9 6 10 9
719092922 77021920 539975779 254719514 967592487 476893866 368936979 465399362 342544824 540338192 42663741 165480608 616996494 16552706 590788849 221462860

输出 #3

817852305 0 0 0 711863206 253280203 896552049 935714838 409506220 592088114 0 413190742 0 363914270 0 14254803

输入输出样例 #4

输入 #4

24 100000000007
19 10 19 15 1 20 13 15 8 23 22 16 19 22 2 20 12 19 17 20 16 8 23 6
944071276 364842194 5376942 671161415 477159272 339665353 176192797 2729865 676292280 249875565 259803120 103398285 466932147 775082441 720192643 535473742 263795756 898670859 476980306 12045411 620291602 593937486 761132791 746546443

输出 #4

918566373 436241503 0 0 0 455245534 0 356196743 0 906000633 0 268983266 21918337 0 733763572 173816039 754920403 0 273067118 205350062 0 566217111 80141532 0

说明/提示

约束

• $1\leq N\leq 2\times10^5$
• $1\leq K\leq 10^{18}$
• $K$ 不是 $998244353$ 的倍数
• $1\leq A_i\leq N\ (1\leq i\leq N)$
• $0\leq B_i<998244353\ (1\leq i\leq N)$
• 输入均为整数

样例解释 1

当操作进行 $2$ 次时，每个高桥君手中的球数如下：

如果选择 $x=1$，每个人手中的球数分别为 $4,0,1,2,5$。
如果选择 $x=2$，每个人手中的球数分别为 $2,0,4,1,5$。
因此，期望值分别为 $3,0,\dfrac{5}{2},\dfrac{3}{2},5$。
对 $998244353$ 取模后分别为 $3,0,499122179,499122178,5$，请按顺序空格分隔输出。

样例解释 2

操作进行 $1$ 次或更多次后，所有球都会被第 $1$ 个高桥君持有。

由 ChatGPT 4.1 翻译