CF2260G Sortable Permutations

一个大小为 $n$ 的排列是指长度为 $n$ 的数组，其中每个整数 $1$ 到 $n$ 恰好出现一次。 我们称一个排列是“可排序的”，如果存在一个整数 $x\ge 2$ 满足以下性质：如果从该排列中移除所有位置为 $x$ 的倍数的元素，那么剩下的数组是严格递增的。换句话说，将第 $x, 2x, 3x,\ldots$（不超过 $n$）个位置的元素移除，保留其余元素的相对顺序，要求剩下的数组严格递增。位置编号从 $1$ 开始。 请计算大小为 $n$ 的可排序排列的数量。由于答案可能非常大，请输出对 $998244353$ 取模后的结果。

一行包含一个整数 $n$（$1\le n\le 2\times 10^5$）——排列的大小。

输出一个整数，表示大小为 $n$ 的可排序排列数量，对 $998244353$ 取模后的结果。

在第一个样例中，唯一的排列是 $[1]$。对于 $x=2$，没有元素被移除，序列自身已经有序。 在第二个样例中，可排序的排列有 $[1,2,3]$，$[1,3,2]$，$[2,1,3]$ 以及 $[2,3,1]$。例如，对于排列 $[2,1,3]$， $x=2$ 有效：去除第 $2$ 个元素后，剩下的序列为 $[2,3]$，是递增的。 在第三个样例中，有一个可排序的排列为 $[1,3,6,4,5,2]$。对于 $x=3$，去除第 $3$ 和第 $6$ 个元素后，剩下严格递增序列 $[1,3,4,5]$。 由 ChatGPT 5 翻译