ACAC 题库 ac.isam.top
GitHub
SMBC 编程竞赛 #2（第 481 场 AtCoder Beginner Contest）
G
半烤煎饼
Half-Baked
AtCoder
⌀ 2653
原题
← F→

半烤煎饼AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

You have decided to bake $N$ pancakes and stack them into one pile.

你决定烤 $N$ 个煎饼，并把它们叠成一摞。AI (CI翻译)

When the $i$-th pancake is baked, its size becomes $A_i$ with probability $1/2$ and $B_i$ with probability $1/2$. These events are independent across pancakes.

烤好第 $i$ 个煎饼后，它的尺寸以 $1/2$ 的概率变为 $A_i$，以 $1/2$ 的概率变为 $B_i$。每个煎饼的结果相互独立。AI (CI翻译)

After baking all $N$ pancakes, you stack them into one pile so that their sizes are in ascending order from the top.

烤好所有 $N$ 个煎饼后，将它们叠成一摞，使得从顶部到底部，煎饼的尺寸按升序排列。AI (CI翻译)

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) \times 2^N$ is an integer.

令 $f(k)$ 表示从顶部数第 $k$ 个煎饼的尺寸的期望值。可以证明，$f(k) \times 2^N$ 是整数。AI (CI翻译)

For $k=1,\dots,N$, find the value of $\left( f(k) \times 2^N \right) \bmod 998244353$.

对于 $k=1,\dots,N$，求 $\left( f(k) \times 2^N \right) \bmod 998244353$。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)
  • $1 \leq N \leq 120\,000$
  • $1 \leq A_i < B_i < 998244353$
  • All input values are integers.
  • $1 \leq N \leq 120\,000$
  • $1 \leq A_i < B_i < 998244353$
  • 输入的所有数值均为整数。
AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

N
A_1 B_1
\vdots
A_N B_N

N
A_1 B_1
\vdots
A_N B_N
AI (CI翻译)

Output

输出格式

AI (CI翻译)

Print $N$ lines. The $l$-th line ($1 \leq l \leq N$) should contain the answer for $k=l$.

输出 $N$ 行。第 $l$ 行（$1 \leq l \leq N$）应包含 $k=l$ 时的答案。AI (CI翻译)

样例

Input #1
3
1000 3000
5000 8000
2000 9000
Output #1
14000
36000
62000
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. - $\displaystyle f(1) = \frac{1000+1000+1000+1000+2000+3000+2000+3000}{8} = 1750$ - $\displaystyle f(2) = \frac{2000+5000+2000+8000+3000+5000+3000+8000}{8} = 4500$ - $\displaystyle f(3) = \frac{5000+9000+8000+9000+5000+9000+8000+9000}{8} = 7750$
Input #2
5
1 2
2 4
2 6
2 8
2 10
Output #2
48
68
92
156
260
Input #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
Output #3
276177791
934318446
44503192
525981255
598596982
938987475
225190244
12980826
379197102
651032077
502004535
311899162
754356358
457449763
807861939
196627040
题目信息
题号
abc481_g
所属比赛
SMBC 编程竞赛 #2（第 481 场 AtCoder Beginner Contest）
时间限制
4 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。