以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Problem M
Zig-zag
Time limit: 12 seconds
Zack’s Zergonomics Zegree has taught him that the optimal way to display items in a store is to stack them into a
zig-zag pattern.
Zack needs to display n boxes lined up on the storefront, each one containing an action figure. These boxes can be
stacked on top of one another, and they are identical and indistinguishable from each other. His goal is to decide the
number of stacks, and then stack up the boxes such that each stack is non-empty, and the numbers of boxes in the
stacks form a zig-zag sequence.
Formally, if there are s (s ≥1) stacks numbered 1 to s from left to right, and stack i contains ai boxes, then the
following conditions must be satisfied:
• ai ≥1 for each i from 1 to s,
• a1 + a2 + . . . + as = n, and
• at least one of the following is true:
• a1 < a2 > a3 < a4 > . . ., or
• a1 > a2 < a3 > a4 < . . .
For example, for n = 6, there are 12 ways as illustrated by Figure M.1.
1 2 3 4 5 6 7 8 9 10 11 12
Figure M.1: All 12 possible ways for n = 6.
Find the number of different ways Zack can stack n boxes modulo 998 244 353.
Two ways are considered the same if and only if the number of stacks is the same, and pairs of stacks at the same
positions have the same number of boxes.
Input
The first line of input contains one integer t (1 ≤t ≤300 000) representing the number of test cases. After that, t test
cases follow. Each of them consists of a single line containing one integer n (1 ≤n ≤300 000).
Output
For each test case, output an integer representing the number of different ways to stack n boxes modulo 998 244 353.
ICPC Asia Pacific Championship 2024 Problem M: Zig-zag
Sample Input #1 Sample Output #1
4 7
5 12
6 19
7 502674609
890
Explanation for the sample input/output #1
The value of n on the second test case is 6, and the 12 ways are illustrated in the problem description.
ICPC Asia Pacific Championship 2024 Problem M: Zig-zag