103106: [Atcoder]ABC310 G - Takahashi And Pass-The-Ball Game
Description
Score : $550$ points
Problem Statement
There are $N$ Takahashi.
The $i$-th Takahashi has an integer $A_i$ and $B_i$ balls.
An integer $x$ between $1$ and $K$, inclusive, will be chosen uniformly at random, and they will repeat the following operation $x$ times.
- For every $i$, the $i$-th Takahashi gives all his balls to the $A_i$-th Takahashi.
Beware that all $N$ Takahashi simultaneously perform this operation.
For each $i=1,2,\ldots,N$, find the expected value, modulo $998244353$, of the number of balls the $i$-th Takahashi has at the end of the operations.
How to find a expected value modulo $998244353$
It can be proved that the sought probability is always a rational number. Additionally, the constraints of this problem guarantee that if the sought probability is represented as an irreducible fraction $\frac{y}{x}$, then $x$ is not divisible by $998244353$. Here, there is a unique $0\leq z\lt998244353$ such that $y\equiv xz\pmod{998244353}$, so report this $z$.Constraints
- $1\leq N\leq 2\times10^5$
- $1\leq K\leq 10^{18}$
- $K$ is not a multiple of $998244353$.
- $1\leq A _ i\leq N\ (1\leq i\leq N)$
- $0\leq B _ i\lt998244353\ (1\leq i\leq N)$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $K$ $A _ 1$ $A _ 2$ $\cdots$ $A _ N$ $B _ 1$ $B _ 2$ $\cdots$ $B _ N$
Output
Print the expected value of the number of balls the $i$-th Takahashi has at the end of the operations for $i=1,2,\ldots,N$, separated by spaces, in a single line.
Sample Input 1
5 2 3 1 4 1 5 1 1 2 3 5
Sample Output 1
3 0 499122179 499122178 5
During two operations, the five Takahashi have the following number of balls.
If $x=1$ is chosen, the five Takahashi have $4,0,1,2,5$ balls.
If $x=2$ is chosen, the five Takahashi have $2,0,4,1,5$ balls.
Thus, the sought expected values are $3,0,\dfrac52,\dfrac32,5$. Print these values modulo $998244353$, that is, $3,0,499122179,499122178,5$, separated by spaces.
Sample Input 2
3 1000 1 1 1 1 10 100
Sample Output 2
111 0 0
After one or more operations, the first Takahashi gets all balls.
Sample Input 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
Sample Output 3
817852305 0 0 0 711863206 253280203 896552049 935714838 409506220 592088114 0 413190742 0 363914270 0 14254803
Sample Input 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
Sample Output 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
Input
Output
问题描述
有$N$个高桥。
第$i$个高桥有整数$A_i$和$B_i$个球。
将从$1$到$K$（包括$1$和$K$）中均匀随机选择一个整数$x$，并重复执行$x$次以下操作。
- 对于每个$i$，第$i$个高桥将他所有的球都给第$A_i$个高桥。
请注意，所有$N$个高桥同时执行此操作。
对于每个$i=1,2,\ldots,N$，求第$i$个高桥在操作结束时持有的球数的期望值，对$998244353$取模。
如何找到对$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=1,2,\ldots,N$时，第$i$个高桥在操作结束时持有的球数的期望值。
样例输入1
5 2 3 1 4 1 5 1 1 2 3 5
样例输出1
3 0 499122179 499122178 5
在两次操作中，五个高桥持有的球数如下。
如果选择$x=1$，五个高桥持有的球数为$4,0,1,2,5$。
如果选择$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 566