304861: CF923E. Perpetual Subtraction
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Perpetual Subtraction
题意翻译
- 黑板上有一个整数 $x$,初始时它的值为 $[0,n]$ 中的某一个整数,其中为 $i$ 的概率是 $p_i$。 - 每一轮你可以将 $x$ 完全随机地替换成 $[0,x]$ 中的一个数。 - 求 $m$ 轮后,对于每个 $i\in[0,n]$,$x=i$ 的概率。 - $n \le 10^5$,$m \le 10^{18}$,答案对 $998244353$ 取模。题目描述
There is a number $ x $ initially written on a blackboard. You repeat the following action a fixed amount of times: 1. take the number $ x $ currently written on a blackboard and erase it 2. select an integer uniformly at random from the range $ [0,x] $ inclusive, and write it on the blackboard Determine the distribution of final number given the distribution of initial number and the number of steps.输入输出格式
输入格式
The first line contains two integers, $ N $ ( $ 1<=N<=10^{5} $ ) — the maximum number written on the blackboard — and $ M $ ( $ 0<=M<=10^{18} $ ) — the number of steps to perform. The second line contains $ N+1 $ integers $ P_{0},P_{1},...,P_{N} $ ( $ 0<=P_{i}<998244353 $ ), where $ P_{i} $ describes the probability that the starting number is $ i $ . We can express this probability as irreducible fraction $ P/Q $ , then ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF923E/78b3a8654b742b81f434340c46c8ad67c1db13e6.png). It is guaranteed that the sum of all $ P_{i} $ s equals $ 1 $ (modulo $ 998244353 $ ).
输出格式
Output a single line of $ N+1 $ integers, where $ R_{i} $ is the probability that the final number after $ M $ steps is $ i $ . It can be proven that the probability may always be expressed as an irreducible fraction $ P/Q $ . You are asked to output ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF923E/95a42f726095d243076c95d92a6f5a7c8a8abc93.png).
输入输出样例
输入样例 #1
2 1
0 0 1
输出样例 #1
332748118 332748118 332748118
输入样例 #2
2 2
0 0 1
输出样例 #2
942786334 610038216 443664157
输入样例 #3
9 350
3 31 314 3141 31415 314159 3141592 31415926 314159265 649178508
输出样例 #3
822986014 12998613 84959018 728107923 939229297 935516344 27254497 413831286 583600448 442738326