← 返回题目列表

AtCoder · utpc2021_j

J. 你喜欢间隔调度问题吗?

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

配点 : 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

此测试用例不包含在小部分分数中。