English · Original
Chinese · Translation
Formal · Original
PolandBall is standing in a row with Many Other Balls. More precisely, there are exactly _n_ Balls. Balls are proud of their home land — and they want to prove that it's strong.
The Balls decided to start with selecting exactly _m_ groups of Balls, each consisting either of single Ball or two neighboring Balls. Each Ball can join no more than one group.
The Balls really want to impress their Enemies. They kindly asked you to calculate number of such divisions for all _m_ where 1 ≤ _m_ ≤ _k_. Output all these values modulo 998244353, the Enemies will be impressed anyway.
## Input
There are exactly two numbers _n_ and _k_ (1 ≤ _n_ ≤ 109, 1 ≤ _k_ < 215), denoting the number of Balls and the maximim number of groups, respectively.
## Output
You should output a sequence of _k_ values. The _i_\-th of them should represent the sought number of divisions into exactly _i_ groups, according to PolandBall's rules.
[samples]
## Note
In the first sample case we can divide Balls into groups as follows:
{1}, {2}, {3}, {12}, {23}.
{12}{3}, {1}{23}, {1}{2}, {1}{3}, {2}{3}.
{1}{2}{3}.
Therefore, output is: _5 5 1_.
PolandBall 站在一排中，与许多其他球在一起。更准确地说，恰好有 #cf_span[n] 个球。这些球为自己的祖国感到自豪 —— 它们想证明自己的国家很强壮。
这些球决定先选出恰好 #cf_span[m] 个球组，每个组由一个球或两个相邻的球组成。每个球最多只能加入一个组。
这些球非常想给敌人留下深刻印象。他们诚恳地请求你计算出对于所有 #cf_span[1 ≤ m ≤ k] 的这种划分方案数。请输出所有这些值对 #cf_span[998244353] 取模的结果，敌人无论如何都会被震撼。
输入中恰好有两个数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 109]，#cf_span[1 ≤ k < 215]），分别表示球的数量和最大组数。
你需要输出一个包含 #cf_span[k] 个值的序列。第 #cf_span[i] 个值应表示根据 PolandBall 的规则，将球划分为恰好 #cf_span[i] 个组的方案数。
在第一个样例中，我们可以将球划分为如下组：
#cf_span[{1}], #cf_span[{2}], #cf_span[{3}], #cf_span[{12}], #cf_span[{23}].
#cf_span[{12}{3}], #cf_span[{1}{23}], #cf_span[{1}{2}], #cf_span[{1}{3}], #cf_span[{2}{3}].
#cf_span[{1}{2}{3}].
因此，输出为：_5 5 1_。
## Input
输入中恰好有两个数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 109]，#cf_span[1 ≤ k < 215]），分别表示球的数量和最大组数。
## Output
你应该输出一个包含 #cf_span[k] 个值的序列。第 #cf_span[i] 个值应表示根据 PolandBall 的规则，将球划分为恰好 #cf_span[i] 个组的方案数。
[samples]
## Note
在第一个样例中，我们可以将球划分为如下组：#cf_span[{1}], #cf_span[{2}], #cf_span[{3}], #cf_span[{12}], #cf_span[{23}].#cf_span[{12}{3}], #cf_span[{1}{23}], #cf_span[{1}{2}], #cf_span[{1}{3}], #cf_span[{2}{3}].#cf_span[{1}{2}{3}].因此，输出为：_5 5 1_。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of balls in a row, and $ k \in \mathbb{Z}^+ $ with $ k < 2^{15} $.
Let $ a_{m} $ denote the number of ways to partition the $ n $ balls into exactly $ m $ disjoint groups, where each group is either a single ball or a pair of two adjacent balls, and each ball belongs to at most one group.
**Constraints**
1. $ 1 \leq n \leq 10^9 $
2. $ 1 \leq k < 2^{15} $
**Objective**
For each $ m \in \{1, 2, \dots, k\} $, compute:
$$
a_m = \sum_{i=0}^{\min(m, n-m)} \binom{n - m}{i} \binom{m}{i} \mod 998244353
$$
and output the sequence $ (a_1, a_2, \dots, a_k) $.
API Response (JSON)
{
"problem": {
"name": "G. PolandBall and Many Other Balls",
"description": {
"content": "PolandBall is standing in a row with Many Other Balls. More precisely, there are exactly _n_ Balls. Balls are proud of their home land — and they want to prove that it's strong. The Balls decided to ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 6000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF755G"
},
"statements": [
{
"statement_type": "Markdown",
"content": "PolandBall is standing in a row with Many Other Balls. More precisely, there are exactly _n_ Balls. Balls are proud of their home land — and they want to prove that it's strong.\n\nThe Balls decided to ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "PolandBall 站在一排中，与许多其他球在一起。更准确地说，恰好有 #cf_span[n] 个球。这些球为自己的祖国感到自豪 —— 它们想证明自己的国家很强壮。\n\n这些球决定先选出恰好 #cf_span[m] 个球组，每个组由一个球或两个相邻的球组成。每个球最多只能加入一个组。\n\n这些球非常想给敌人留下深刻印象。他们诚恳地请求你计算出对于所有 #cf_span[1 ≤ m ≤ k] 的这种划...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of balls in a row, and $ k \\in \\mathbb{Z}^+ $ with $ k < 2^{15} $. \nLet $ a_{m} $ denote the number of ways to partition the $ n $ balls int...",
"is_translate": false,
"language": "Formal"
}
]
}