English · Original
Chinese · Translation
Formal · Original
The Floral Clock has been standing by the side of Mirror Lake for years. Though unable to keep time, it reminds people of the passage of time and the good old days.
On the rim of the Floral Clock are 2_n_ flowers, numbered from 1 to 2_n_ clockwise, each of which has a colour among all _n_ possible ones. For each colour, there are exactly two flowers with it, the distance between which **either is less than or equal to 2, or equals _n_**. Additionally, if flowers _u_ and _v_ are of the same colour, then flowers opposite to _u_ and opposite to _v_ should be of the same colour as well — symmetry is beautiful!
Formally, the distance between two flowers is 1 plus the number of flowers on the minor arc (or semicircle) between them. Below is a possible arrangement with _n_ = 6 that cover all possibilities.
<center></center>The beauty of an arrangement is defined to be the product of the lengths of flower segments separated by all opposite flowers of the same colour. In other words, in order to compute the beauty, we remove from the circle all flowers that have the same colour as flowers opposite to them. Then, the beauty is the product of lengths of all remaining segments. Note that we include segments of length 0 in this product. If there are no flowers that have the same colour as flower opposite to them, the beauty equals 0. For instance, the beauty of the above arrangement equals 1 × 3 × 1 × 3 = 9 — the segments are {2}, {4, 5, 6}, {8} and {10, 11, 12}.
While keeping the constraints satisfied, there may be lots of different arrangements. Find out the sum of beauty over all possible arrangements, modulo 998 244 353. Two arrangements are considered different, if a pair (_u_, _v_) (1 ≤ _u_, _v_ ≤ 2_n_) exists such that flowers _u_ and _v_ are of the same colour in one of them, but not in the other.
## Input
The first and only line of input contains a lonely positive integer _n_ (3 ≤ _n_ ≤ 50 000) — the number of colours present on the Floral Clock.
## Output
Output one integer — the sum of beauty over all possible arrangements of flowers, modulo 998 244 353.
[samples]
## Note
With _n_ = 3, the following six arrangements each have a beauty of 2 × 2 = 4.
<center></center>While many others, such as the left one in the figure below, have a beauty of 0. The right one is invalid, since it's asymmetric.
<center></center>
花钟多年来一直伫立在镜湖之畔。虽然无法准确计时，但它提醒着人们时光的流逝与美好的往昔。
花钟的边缘上有 #cf_span[2n] 朵花，按顺时针方向编号为 #cf_span[1] 到 #cf_span[2n]，每朵花的颜色属于全部 #cf_span[n] 种可能颜色之一。对于每种颜色，恰好有两朵花具有该颜色，这两朵花之间的 #cf_span(class=[tex-font-style-underline], body=[distance]) 要么小于等于 #cf_span[2]，要么等于 #cf_span[n]。此外，如果花朵 #cf_span[u] 和 #cf_span[v] 颜色相同，则与 #cf_span[u] 和 #cf_span[v] 相对的花朵也必须颜色相同——对称才是美丽的！
形式化地，两朵花之间的 #cf_span(class=[tex-font-style-underline], body=[distance]) 定义为 #cf_span[1] 加上它们之间劣弧（或半圆）上的花朵数量。下图展示了一个满足所有条件的 #cf_span[n = 6] 的可能排列。
一个排列的 #cf_span(class=[tex-font-style-underline], body=[beauty]) 定义为：由所有与对面花朵颜色相同的花朵所分割出的花段长度的乘积。换句话说，为了计算美丽值，我们从圆圈中移除所有颜色与对面花朵颜色相同的花。然后，美丽值等于所有剩余花段长度的乘积。注意，我们包含长度为 #cf_span[0] 的段。如果没有花的颜色与其对面花的颜色相同，则美丽值为 #cf_span[0]。例如，上图排列的 #cf_span(class=[tex-font-style-underline], body=[beauty]) 为 #cf_span[1 × 3 × 1 × 3 = 9]，对应的花段为 #cf_span[{2}]、#cf_span[{4, 5, 6}]、#cf_span[{8}] 和 #cf_span[{10, 11, 12}]。
在满足上述约束的前提下，可能存在许多不同的排列。请计算所有可能排列的 #cf_span(class=[tex-font-style-underline], body=[beauty]) 之和，对 #cf_span[998 244 353] 取模。两个排列被认为是不同的，当且仅当存在一对 #cf_span[(u, v)]（#cf_span[1 ≤ u, v ≤ 2n]），使得在一排列中 #cf_span[u] 和 #cf_span[v] 颜色相同，而在另一排列中则不同。
输入仅包含一行，一个正整数 #cf_span[n]（#cf_span[3 ≤ n ≤ 50 000]），表示花钟上存在的颜色种类数。
输出一个整数——所有可能花排列的 #cf_span(class=[tex-font-style-underline], body=[beauty]) 之和，对 #cf_span[998 244 353] 取模。
当 #cf_span[n = 3] 时，以下六种排列每种的 #cf_span(class=[tex-font-style-underline], body=[beauty]) 均为 #cf_span[2 × 2 = 4]。
而许多其他排列，例如下图左侧的排列，其 #cf_span(class=[tex-font-style-underline], body=[beauty]) 为 #cf_span[0]。右侧的排列无效，因为它不对称。
## Input
输入仅包含一行，一个正整数 #cf_span[n]（#cf_span[3 ≤ n ≤ 50 000]），表示花钟上存在的颜色种类数。
## Output
输出一个整数——所有可能花排列的 #cf_span(class=[tex-font-style-underline], body=[beauty]) 之和，对 #cf_span[998 244 353] 取模。
[samples]
## Note
当 #cf_span[n = 3] 时，以下六种排列每种的 #cf_span(class=[tex-font-style-underline], body=[beauty]) 均为 #cf_span[2 × 2 = 4]。而许多其他排列，例如下图左侧的排列，其 #cf_span(class=[tex-font-style-underline], body=[beauty]) 为 #cf_span[0]。右侧的排列无效，因为它不对称。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ with $ 3 \leq n \leq 50000 $.
Let the Floral Clock consist of $ 2n $ flowers arranged in a circle, labeled $ 1 $ to $ 2n $ clockwise.
There are $ n $ distinct colors; each color appears on exactly two flowers.
Let $ \text{opp}(i) = i + n \mod 2n $ (with labels taken modulo $ 2n $, adjusted to $ \{1, \dots, 2n\} $) denote the flower opposite to flower $ i $.
**Constraints**
1. For each color, the two flowers having it must satisfy:
- Their circular distance (defined as $ 1 + $ number of flowers on the minor arc between them) is either $ \leq 2 $, or exactly $ n $.
2. **Symmetry constraint**: If flowers $ u $ and $ v $ have the same color, then $ \text{opp}(u) $ and $ \text{opp}(v) $ must also have the same color.
**Beauty Definition**
For a valid arrangement:
- Let $ S $ be the set of flowers $ i $ such that flower $ i $ and flower $ \text{opp}(i) $ have the *same* color.
- Remove all flowers in $ S $ from the circle.
- The circle breaks into contiguous segments of remaining flowers.
- The **beauty** is the product of the lengths of all these segments (including length-0 segments).
- If no such $ i $ exists (i.e., $ S = \emptyset $), beauty = 0.
**Objective**
Compute the sum of beauty over all valid arrangements, modulo $ 998244353 $.
API Response (JSON)
{
"problem": {
"name": "E. Days of Floral Colours",
"description": {
"content": "The Floral Clock has been standing by the side of Mirror Lake for years. Though unable to keep time, it reminds people of the passage of time and the good old days. On the rim of the Floral Clock are",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 7000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF848E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "The Floral Clock has been standing by the side of Mirror Lake for years. Though unable to keep time, it reminds people of the passage of time and the good old days.\n\nOn the rim of the Floral Clock are...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "花钟多年来一直伫立在镜湖之畔。虽然无法准确计时，但它提醒着人们时光的流逝与美好的往昔。\n\n花钟的边缘上有 #cf_span[2n] 朵花，按顺时针方向编号为 #cf_span[1] 到 #cf_span[2n]，每朵花的颜色属于全部 #cf_span[n] 种可能颜色之一。对于每种颜色，恰好有两朵花具有该颜色，这两朵花之间的 #cf_span(class=[tex-font-style-under...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ with $ 3 \\leq n \\leq 50000 $. \nLet the Floral Clock consist of $ 2n $ flowers arranged in a circle, labeled $ 1 $ to $ 2n $ clockwise. \nThere are $ n $ d...",
"is_translate": false,
"language": "Formal"
}
]
}