← 返回题目列表

AtCoder · jsc2022_final_g

G. 二分分区

中文机器翻译题面 查看原题

配点 : 1600 点

問題文

整数 N 。 编号高达 1 减去 N 编号最多为 N 由顶点组成的无向图 考虑 G 。 满足以下所有条件的图 G 的数量 除以 998244353 求余数。

  • G 不包含多个边或自循环。
  • G 是一个串联。 分割
  • G 的顶点集 存在满足以下条件的 \{S_1,S_2,\cdots\} 。 关于
    • 各 S_i ,|S_i| \geq 2 。
    • 各 S_i ,S_i 导出的子图是一个连通的二分图。
什么是诱导子图? 图

S 让它成为 G 顶点的子集。 这时,G 的 S 的引导子图是一个顶点集为 S 且边缘设置为``G 有两端的一侧 这是一张“ S 中包含的所有内容”的图表。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 所有输入值均为整数

入力

输入是按以下格式从标准输入给出的。

N

出力

打印答案。


入力例 1

2

出力例 1

1

入力例 2

3

出力例 2

3

入力例 3

4

出力例 3

38

入力例 4

5

出力例 4

712

入力例 5

12345

出力例 5

503682022