E. Perpetual Subtraction

Codeforces

IDCF923E

Time2000ms

Memory256MB

Difficulty—

fftmathmatrices

English · Original

Chinese · Translation

Formal · Original

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. ## Input The first line contains two integers, _N_ (1 ≤ _N_ ≤ 105) — the maximum number written on the blackboard — and _M_ (0 ≤ _M_ ≤ 1018) — 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 . It is guaranteed that the sum of all _P__i_s equals 1 (modulo 998244353). ## Output 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 . [samples] ## Note In the first case, we start with number 2. After one step, it will be 0, 1 or 2 with probability 1/3 each. In the second case, the number will remain 2 with probability 1/9. With probability 1/9 it stays 2 in the first round and changes to 1 in the next, and with probability 1/6 changes to 1 in the first round and stays in the second. In all other cases the final integer is 0.

黑板上最初写有一个数字 #cf_span[x]。你将重复以下操作固定次数：给定初始数字的分布和操作步数，求最终数字的分布。第一行包含两个整数，#cf_span[N] (#cf_span[1 ≤ N ≤ 105]) —— 黑板上可能写出的最大数字，以及 #cf_span[M] (#cf_span[0 ≤ M ≤ 1018]) —— 要执行的操作步数。第二行包含 #cf_span[N + 1] 个整数 #cf_span[P0, P1, ..., PN] (#cf_span[0 ≤ Pi < 998244353])，其中 #cf_span[Pi] 表示初始数字为 #cf_span[i] 的概率。我们可以将该概率表示为最简分数 #cf_span[P / Q]，则。保证所有 #cf_span[Pi] 之和等于 #cf_span[1]（模 #cf_span[998244353]）。请输出一行 #cf_span[N + 1] 个整数，其中 #cf_span[Ri] 表示经过 #cf_span[M] 步后最终数字为 #cf_span[i] 的概率。可以证明，该概率总能表示为最简分数 #cf_span[P / Q]。你需输出。在第一个例子中，我们从数字 2 开始。经过一步后，它将以各 1/3 的概率变为 0、1 或 2。在第二个例子中，数字以概率 1/9 保持为 2。以概率 1/9，它在第一轮保持为 2，第二轮变为 1；以概率 1/6，它在第一轮变为 1，第二轮保持不变。在所有其他情况下，最终整数为 0。 ## Input 第一行包含两个整数，#cf_span[N] (#cf_span[1 ≤ N ≤ 105]) —— 黑板上可能写出的最大数字，以及 #cf_span[M] (#cf_span[0 ≤ M ≤ 1018]) —— 要执行的操作步数。第二行包含 #cf_span[N + 1] 个整数 #cf_span[P0, P1, ..., PN] (#cf_span[0 ≤ Pi < 998244353])，其中 #cf_span[Pi] 表示初始数字为 #cf_span[i] 的概率。我们可以将该概率表示为最简分数 #cf_span[P / Q]，则。保证所有 #cf_span[Pi] 之和等于 #cf_span[1]（模 #cf_span[998244353]）。 ## Output 请输出一行 #cf_span[N + 1] 个整数，其中 #cf_span[Ri] 表示经过 #cf_span[M] 步后最终数字为 #cf_span[i] 的概率。可以证明，该概率总能表示为最简分数 #cf_span[P / Q]。你需输出。 [samples] ## Note 在第一个例子中，我们从数字 2 开始。经过一步后，它将以各 1/3 的概率变为 0、1 或 2。在第二个例子中，数字以概率 1/9 保持为 2。以概率 1/9，它在第一轮保持为 2，第二轮变为 1；以概率 1/6，它在第一轮变为 1，第二轮保持不变。在所有其他情况下，最终整数为 0。

**Definitions** Let $ N \in \mathbb{Z}^+ $, $ M \in \mathbb{Z}_{\geq 0} $. Let $ \mathbf{P} = (P_0, P_1, \dots, P_N) \in \mathbb{F}_{998244353}^{N+1} $ be the initial probability distribution, where $ P_i = \mathbb{P}(\text{initial number} = i) $. Let $ \mathbf{R}^{(M)} = (R_0^{(M)}, R_1^{(M)}, \dots, R_N^{(M)}) \in \mathbb{F}_{998244353}^{N+1} $ be the final probability distribution after $ M $ steps. Let $ T \in \mathbb{F}_{998244353}^{(N+1) \times (N+1)} $ be the transition matrix defined by: $$ T_{i,j} = \mathbb{P}(\text{next number} = j \mid \text{current number} = i) = \begin{cases} \frac{1}{i+1} & \text{if } 0 \leq j \leq i \\ 0 & \text{otherwise} \end{cases} $$ **Constraints** 1. $ 1 \leq N \leq 10^5 $ 2. $ 0 \leq M \leq 10^{18} $ 3. $ \sum_{i=0}^N P_i \equiv 1 \pmod{998244353} $ 4. $ 0 \leq P_i < 998244353 $ for all $ i $ **Objective** Compute: $$ \mathbf{R}^{(M)} = \mathbf{P}^\top \cdot T^M $$ Output $ R_0^{(M)}, R_1^{(M)}, \dots, R_N^{(M)} $ modulo $ 998244353 $.

Samples

Input #1

2 1
0 0 1

Output #1

332748118 332748118 332748118

Input #2

2 2
0 0 1

Output #2

942786334 610038216 443664157

Input #3

9 350
3 31 314 3141 31415 314159 3141592 31415926 314159265 649178508

Output #3

822986014 12998613 84959018 728107923 939229297 935516344 27254497 413831286 583600448 442738326

API Response (JSON)

{
  "problem": {
    "name": "E. Perpetual Subtraction",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF923E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a number _x_ initially written on a blackboard. You repeat the following action a fixed amount of times:\n\n1.  take the number _x_ currently written on a blackboard and erase it\n2.  select an ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "黑板上最初写有一个数字 #cf_span[x]。你将重复以下操作固定次数：\n\n给定初始数字的分布和操作步数，求最终数字的分布。\n\n第一行包含两个整数，#cf_span[N] (#cf_span[1 ≤ N ≤ 105]) —— 黑板上可能写出的最大数字，以及 #cf_span[M] (#cf_span[0 ≤ M ≤ 1018]) —— 要执行的操作步数。\n\n第二行包含 #cf_span[N + ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $, $ M \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ \\mathbf{P} = (P_0, P_1, \\dots, P_N) \\in \\mathbb{F}_{998244353}^{N+1} $ be the initial probability distribution, whe...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments