← 返回题目列表

AtCoder · abc310_g

G. 高桥和传球游戏

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

分数: 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