T121450 [Cnoi2020] 明天后的幻想乡

纸片的末尾写着这样一个问题: 有一个数列 $\{1,2,3,...,n\}$, 求问它有多少个子序列是**等比数列**。 答案对 $998244353$ 取模。

一个正整数 $n$。

一个正整数，表示答案对 $998244353$ 取模后的结果。

### Sample1说明 $\{1,2,4\}$,$\{1,3,9\}$,$\{2,4,8\}$,$\{4,6,9\}$,$\{1,2,4,8\}$ 满足条件。 ### 数据范围约定 : **「本题采用捆绑测试」** - Subtask1( $20\%$ ) : $n \le 30$ - Subtask2( $20\%$ ) : $n \le 10^3$ - Subtask3( $20\%$ ) : $n \le 10^6$ - Subtask4( $10\%$ ) : $n \le 10^8$ - Subtask5( $10\%$ ) : $n \le 10^{10}$ - Subtask6( $20\%$ ) : $n \le 10^{12}$ 对于 $100\%$ 的数据 : $n \in (0,10^{12}]$ ### 后置数学知识 - **等比数列** : 从第二项起，每一项与它的前一项的比值等于同一个常数的数列。本题认为如果一个数列为等比数列，则其必须**不少于三项**。 ### 后记 - 如果想了解故事背景请参考 ~~《东方人参记》~~《东方年代记》。