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

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $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

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

输出#1

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

说明/提示

约束

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页