← 返回题单
题单练习 动态规划的优化
← 上一题 下一题 →

A7072 | 前向走

时间限制2s
内存限制128MB
通过 / 提交0/0

题目描述

你有一张 $1 \times n$ 的纸带，由 $n$ 个格子组成。初始时，有一个点在第 $n$ 号格子中。

如果当前点在格子 $x$ 上（$x 1$），你可以进行如下两种操作之一：

1. 减法操作：选择一个整数 $y$，满足 $1 \le y \le x - 1$，将点移动到格子 $x - y$；
2. 除法操作：选择一个整数 $z$，满足 $2 \le z \le x$，将点移动到格子 $\left\lfloor \dfrac{x}{z} \right\rfloor$。

当点在 $1$ 号格子中时，无法再进行任何操作，过程结束。

请你计算：将点从 $n$ 号格子移动到 $1$ 号格子的不同方案数，并对给定的模数 $m$ 取模。

两个方案不同，当且仅当在某一步中，选择的操作类型或选择的数字不同。
例如，当 $x = 5$ 时：

  • 选择操作 $1$ 且 $y = 4$；
  • 选择操作 $2$ 且 $z = 3$；
  • 选择操作 $2$ 且 $z = 4$；
  • 选择操作 $2$ 且 $z = 5$；
这些都会把点移动到 $1$ 号格子，但它们被认为是 4 种不同的方案。

输入格式

输入只有一行，包含两个整数 $n,m$：

  • $n$：纸带格子的数量；
  • $m$：模数。

输出格式

输出一行一个整数，表示从格子 $n$ 到格子 $1$ 的方案数对 $m$ 取模后的结果。

输入输出样例

输入 #1
3 998244353
输出 #1
5
输入 #2
5 998244353
输出 #2
25
输入 #3
42 998244353
输出 #3
793019428
输入 #4
787788 100000007
输出 #4
94810539
C++ 编辑器
输入
输出