AT_abc481_g.Half-Baked

NOI/NOI+/CTSC

通过率:0%

时间限制:4.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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

When the ii-th pancake is baked, its size becomes AiA_i with probability 1/21/2 and BiB_i with probability 1/21/2. These events are independent across pancakes.

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

Let f(k)f(k) be the expected value of the size of the kk-th pancake from the top. It can be proved that f(k)×2Nf(k) \times 2^N is an integer.

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

你决定制作 NN 个煎饼,并将它们堆叠成一摞。

第 ii 个煎饼烘烤完成后,其尺寸以概率 1/21/2 变为 AiA_i,以概率 1/21/2 变为 BiB_i。这些事件在不同煎饼之间相互独立。

在全部 NN 个煎饼烘烤完毕后,你将它们堆叠成一摞,使得从上到下尺寸严格递增。

令 f(k)f(k) 表示从顶部数起第 kk 个煎饼的尺寸的期望值。可以证明 f(k)×2Nf(k) \times 2^N 是一个整数。

对 k=1,…,Nk = 1, \dots, N,求 (f(k)×2N) mod 998244353\left( f(k) \times 2^N \right) \bmod 998244353 的值。

输入格式

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

NN
A1A_1 B1B_1
⋮\vdots
ANA_N BNB_N

输入从标准输入中按以下格式给出:

NN
A1A_1 B1B_1
⋮\vdots
ANA_N BNB_N

输出格式

Print NN lines. The ll-th line (1≤l≤N1 \leq l \leq N) should contain the answer for k=lk=l.

输出 NN 行。第 ll 行(1≤l≤N1 \leq l \leq N)应包含 k=lk=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 88 sequences, each with probability 1/81/8.

  • (1000, 2000, 5000)(1000,\ 2000,\ 5000)
  • (1000, 5000, 9000)(1000,\ 5000,\ 9000)
  • (1000, 2000, 8000)(1000,\ 2000,\ 8000)
  • (1000, 8000, 9000)(1000,\ 8000,\ 9000)
  • (2000, 3000, 5000)(2000,\ 3000,\ 5000)
  • (3000, 5000, 9000)(3000,\ 5000,\ 9000)
  • (2000, 3000, 8000)(2000,\ 3000,\ 8000)
  • (3000, 8000, 9000)(3000,\ 8000,\ 9000)

Here, the values of f(1),f(2),f(3)f(1), f(2), f(3) are as follows.

  • f(1)=1000+1000+1000+1000+2000+3000+2000+30008=1750\displaystyle f(1) = \frac{1000+1000+1000+1000+2000+3000+2000+3000}{8} = 1750
  • f(2)=2000+5000+2000+8000+3000+5000+3000+80008=4500\displaystyle f(2) = \frac{2000+5000+2000+8000+3000+5000+3000+8000}{8} = 4500
  • f(3)=5000+9000+8000+9000+5000+9000+8000+90008=7750\displaystyle f(3) = \frac{5000+9000+8000+9000+5000+9000+8000+9000}{8} = 7750

Constraints

  • 1≤N≤120 0001 \leq N \leq 120\,000
  • 1≤Ai<Bi<9982443531 \leq A_i < B_i < 998244353
  • All input values are integers.

样例 1 解释:
从上到下堆叠的煎饼尺寸序列是以下 88 种序列之一,每种序列出现的概率均为 1/81/8。

  • (1000, 2000, 5000)(1000,\ 2000,\ 5000)
  • (1000, 5000, 9000)(1000,\ 5000,\ 9000)
  • (1000, 2000, 8000)(1000,\ 2000,\ 8000)
  • (1000, 8000, 9000)(1000,\ 8000,\ 9000)
  • (2000, 3000, 5000)(2000,\ 3000,\ 5000)
  • (3000, 5000, 9000)(3000,\ 5000,\ 9000)
  • (2000, 3000, 8000)(2000,\ 3000,\ 8000)
  • (3000, 8000, 9000)(3000,\ 8000,\ 9000)

此时,f(1),f(2),f(3)f(1), f(2), f(3) 的值如下所示:

  • f(1)=1000+1000+1000+1000+2000+3000+2000+30008=1750\displaystyle f(1) = \frac{1000+1000+1000+1000+2000+3000+2000+3000}{8} = 1750
  • f(2)=2000+5000+2000+8000+3000+5000+3000+80008=4500\displaystyle f(2) = \frac{2000+5000+2000+8000+3000+5000+3000+8000}{8} = 4500
  • f(3)=5000+9000+8000+9000+5000+9000+8000+90008=7750\displaystyle f(3) = \frac{5000+9000+8000+9000+5000+9000+8000+9000}{8} = 7750

约束条件

  • 1≤N≤120 0001 \leq N \leq 120\,000
  • 1≤Ai<Bi<9982443531 \leq A_i < B_i < 998244353
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页