AT_abc481_g.Half-Baked
NOI/NOI+/CTSC
通过率:0%
时间限制:4.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You have decided to bake N pancakes and stack them into one pile.
When the i-th pancake is baked, its size becomes Ai with probability 1/2 and Bi with probability 1/2. These events are independent across pancakes.
After baking all N pancakes, you stack them into one pile so that their sizes are in ascending order from the top.
Let f(k) be the expected value of the size of the k-th pancake from the top. It can be proved that f(k)×2N is an integer.
For k=1,…,N, find the value of (f(k)×2N)mod998244353.
你决定制作 N 个煎饼,并将它们堆叠成一摞。
第 i 个煎饼烘烤完成后,其尺寸以概率 1/2 变为 Ai,以概率 1/2 变为 Bi。这些事件在不同煎饼之间相互独立。
在全部 N 个煎饼烘烤完毕后,你将它们堆叠成一摞,使得从上到下尺寸严格递增。
令 f(k) 表示从顶部数起第 k 个煎饼的尺寸的期望值。可以证明 f(k)×2N 是一个整数。
对 k=1,…,N,求 (f(k)×2N)mod998244353 的值。
输入格式
The input is given from Standard Input in the following format:
N
A1 B1
⋮
AN BN
输入从标准输入中按以下格式给出:
N
A1 B1
⋮
AN BN
输出格式
Print N lines. The l-th line (1≤l≤N) should contain the answer for k=l.
输出 N 行。第 l 行(1≤l≤N)应包含 k=l 时的答案。
输入输出样例
输入#1
3 1000 3000 5000 8000 2000 9000
输出#1
14000 36000 62000
输入#2
5 1 2 2 4 2 6 2 8 2 10
输出#2
48 68 92 156 260
输入#3
16 590750810 881929947 587037424 967895551 443510128 787944380 689922795 844014120 384247532 471383266 66520009 905781395 927671784 951066952 233378255 857611956 91689637 419605608 280270213 778410686 141205183 456501569 59232352 956004175 150307063 296071558 84333651 869834323 269686721 755659326 152999727 215448458
输出#3
276177791 934318446 44503192 525981255 598596982 938987475 225190244 12980826 379197102 651032077 502004535 311899162 754356358 457449763 807861939 196627040
说明/提示
Sample 1 Explanation:
The sequence of sizes of the stacked pancakes from the top is one of the following 8 sequences, each with probability 1/8.
- (1000, 2000, 5000)
- (1000, 5000, 9000)
- (1000, 2000, 8000)
- (1000, 8000, 9000)
- (2000, 3000, 5000)
- (3000, 5000, 9000)
- (2000, 3000, 8000)
- (3000, 8000, 9000)
Here, the values of f(1),f(2),f(3) are as follows.
- f(1)=81000+1000+1000+1000+2000+3000+2000+3000=1750
- f(2)=82000+5000+2000+8000+3000+5000+3000+8000=4500
- f(3)=85000+9000+8000+9000+5000+9000+8000+9000=7750
Constraints
- 1≤N≤120000
- 1≤Ai<Bi<998244353
- All input values are integers.
样例 1 解释:
从上到下堆叠的煎饼尺寸序列是以下 8 种序列之一,每种序列出现的概率均为 1/8。
- (1000, 2000, 5000)
- (1000, 5000, 9000)
- (1000, 2000, 8000)
- (1000, 8000, 9000)
- (2000, 3000, 5000)
- (3000, 5000, 9000)
- (2000, 3000, 8000)
- (3000, 8000, 9000)
此时,f(1),f(2),f(3) 的值如下所示:
- f(1)=81000+1000+1000+1000+2000+3000+2000+3000=1750
- f(2)=82000+5000+2000+8000+3000+5000+3000+8000=4500
- f(3)=85000+9000+8000+9000+5000+9000+8000+9000=7750
约束条件
- 1≤N≤120000
- 1≤Ai<Bi<998244353
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?