/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
高橋くんが N 人います。
i 番目の高橋くんは、整数 A _ i とボール B _ i 個を持っています。
高橋くんたちは 1 以上 K 以下の整数 x を一様ランダムに選び、次の操作を x 回繰り返します。
- すべての i について、i 番目の高橋くんは A _ i 番目の高橋くんに自分が持っているボールをすべて渡す。
操作は N 人によって同時に行われることに注意してください。
i=1,2,\ldots,N について、一連の操作が終了したとき i 番目の高橋くんが持っているボールの個数の期待値を {}\bmod{998244353} で求めてください。
期待値 {}\bmod{998244353} の定義
この問題で求める期待値は必ず有理数になることが証明できます。 また、この問題の制約下では、求める期待値を既約分数 \frac yx で表したときに x が 998244353 で割り切れないことが保証されます。 このとき、y\equiv xz\pmod{998244353} を満たす 0\leq z\lt998244353 がただ一つ存在するので、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 行に出力せよ。
入力例 1
5 2 3 1 4 1 5 1 1 2 3 5
出力例 1
3 0 499122179 499122178 5
操作を 2 回行うと、それぞれの高橋くんが持っているボールは以下のようになります。
x=1 が選ばれた場合、それぞれの高橋くんが持っているボールの数は 4,0,1,2,5 個です。
x=2 が選ばれた場合、それぞれの高橋くんが持っているボールの数は 2,0,4,1,5 個です。
よって、求める期待値はそれぞれ 3,0,\dfrac52,\dfrac32,5 です。 {}\bmod{998244353} での値を求めるとそれぞれ 3,0,499122179,499122178,5 となるので、これらを順に空白区切りで出力してください。
入力例 2
3 1000 1 1 1 1 10 100
出力例 2
111 0 0
1 回以上操作すると、すべてのボールを 1 番目の高橋くんが持つことになります。
入力例 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
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