配点 : 100 点
問題文
真君考虑了以下问题。
一个区间调度问题
N 间隔 给出了 [L_i,R_i] 给定。请找出可以选择的区间数的最大值,以满足以下条件。
- 选择的区间中,任何两个都没有重叠部分。
制約
- 数列 L 和 按字典顺序比较 R 当中, 1 减去 2N 之前的整数正好是 写了 1 出现了若干次
- L_i < R_i ( 1 \leq i \leq N)
这个问题太典型了,所以热爱计数的照夫君将问题改成了如下形式。
区间调度问题
整数 N 。 对于一个区间调度问题 满足约束的所有输入的解的总和 998244353 后的余数。
区间调度问题 。
制約
- 1 \leq N \leq 2\times 10^5
部分点
这个问题有多个部分点。 如果正确答案是满足
- 1 \le N \le 50 的数据集 给出 10 点。 如果您正确回答了所有满足
- 1 \le N \le 3000 的数据集 给出 30 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N
出力
请将答案输出在一行内。
入力例1
2
出力例1
8
一个区间调度问题 可作为输入的,是以下 6 是的。 请注意,我们正在寻找除以
- L=(1,2), R=(3,4)
- L=(1,2), R=(4,3)
- L=(1,3), R=(2,4)
- L=(2,1), R=(3,4)
- L=(2,1), R=(4,3)
- L=(3,1), R=(4,2)
上記 6 种输入的 一个区间调度问题 答案是 1,1,2,1,1,2 所以, 您最多只能移动到区间调度问题 答案是 1+1+2+1+1+2 该值应乘以 998244353 后的余数 输出 8 。 对于
入力例 2
4
出力例 2
4944
这个测试用例是 10 包含在小部分分数中。
入力例 3
2021
出力例 3
383310824
这个测试用例是 30 包含在小部分分数中。
入力例 4
100000
出力例 4
143469183
此测试用例不包含在小部分分数中。