分数: 550 点
问题陈述
有 N 高桥。
的 i-th Takahashi 有一个整数 A_i 和 B_i 球。
一个整数 x 之间 1 和 K,包含在内,将被随机统一选择,并重复以下操作 x 次。
- 对于每个 i, i-th Takahashi把他所有的球都给了 A_i-高桥。
请注意,所有 N Takahashi 同时执行此操作。
对于每个 i=1,2,\ldots,N,求期望值,取模 998244353,球的数量 i-th Takahashi 已结束操作。
如何求期望值模 998244353
可以证明,求的概率总是有理数。此外,该问题的约束保证如果所寻求的概率表示为不可约分数 \frac{y}{x},那么 x 不能被整除 998244353。 这里,有一种独特的 0\leq z\lt998244353 这样 y\equiv xz\pmod{998244353},所以报告这个 z.约束
- 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\lt998244353\ (1\leq i\leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K A _ 1 A _ 2 \cdots A _ N B _ 1 B _ 2 \cdots B _ N
输出
打印球数的期望值 i-th Takahashi 已结束操作 i=1,2,\ldots,N,以空格分隔,位于一行中。
示例输入 1
5 2 3 1 4 1 5 1 1 2 3 5
示例输出 1
3 0 499122179 499122178 5
在两次操作中,五个高桥拥有以下数量的球。

If x=1 被选中,高桥五人已 4,0,1,2,5 球。
If x=2 被选中,高桥五人已 2,0,4,1,5 球。
因此,寻求的期望值是 3,0,\dfrac52,\dfrac32,5。 打印这些值的模数 998244353,即 3,0,499122179,499122178,5,用空格分隔。
示例输入 2
3 1000 1 1 1 1 10 100
示例输出 2
111 0 0
经过一次或多次操作后,第一个高桥获得所有球。
示例输入 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
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