#P17796. Perpetual Subtraction
Perpetual Subtraction
CF923E Perpetual Subtraction
题目描述
最初黑板上写有一个数字 。你需要重复以下操作若干次:
- 取下当前黑板上的数字 并擦除;
- 从区间 (包含 )中均匀随机选择一个整数,并将其写在黑板上。
给定初始数字的概率分布和操作次数,求经过 次操作后,最终数字的概率分布。
输入格式
第一行包含两个整数 ()——黑板上可能写下的最大数字,以及 ()——需要执行的操作次数。
第二行包含 个整数 (),其中 表示初始数字为 的概率。若概率为最简分数 ,则 。保证所有 之和模 等于 。
输出格式
输出一行共 个整数,第 个数 表示经过 次操作后最终数字为 的概率。概率可表示为最简分数 ,你需要输出 。
输入输出样例 #1
输入 #1
2 1
0 0 1
输出 #1
332748118 332748118 332748118
输入输出样例 #2
输入 #2
2 2
0 0 1
输出 #2
942786334 610038216 443664157
输入输出样例 #3
输入 #3
9 350
3 31 314 3141 31415 314159 3141592 31415926 314159265 649178508
输出 #3
822986014 12998613 84959018 728107923 939229297 935516344 27254497 413831286 583600448 442738326
说明/提示
在第一个样例中,初始数字为 。经过一次操作后,最终数字为 、 或 的概率均为 。
在第二个样例中,数字保持为 的概率为 。有 的概率第一次保持为 ,第二次变为 ,有 的概率第一次变为 ,第二次保持为 。其余情况下最终数字为 。