【MX-S2-T3】 跳

Luogu
IDLGP10812
Time1000ms
Memory512MB
DifficultyP5
动态规划 DPO2优化前缀和梦熊比赛
给定一个坐标轴,范围是 $1\sim n$。每个点 $i$ 可以跳到 $i+1$($i+1\le n$)或 $i-1$($i-1\ge 1$)或他的因子处。每个点只能到达一次。问从点 $n$ 到点 $1$ 一共有多少方案。答案对 $p$ 取模。 两种方案不同当且仅当存在一次跳跃后的位置不同或存在一次跳跃的种类不同。 ## Input 一行两个整数 $n,p$。 ## Output 一行一个整数,表示答案对 $p$ 取模后的结果。 [samples] ## Background 原题链接:<https://oier.team/problems/S2C>。 --- ![](https://cdn.luogu.com.cn/upload/image_hosting/kq7nqgu8.png) ~~跳一跳世界第一。~~ ~~不处,不收徒,差距自己找。~~ ## Note **【样例解释 \#1】** 设 $\rightarrow$ 表示向上或向下跳,$\Rightarrow$ 表示跳因子。共三种方案如下。 + $3\Rightarrow1$ + $3\rightarrow2\rightarrow1$ + $3\rightarrow2\Rightarrow1$ **【样例解释 \#2】** 设 $\rightarrow$ 表示向上或向下跳,$\Rightarrow$ 表示跳因子。共七种方案如下。 + $4\rightarrow3\Rightarrow1$ + $4\rightarrow3\rightarrow2\rightarrow1$ + $4\rightarrow3\rightarrow2\Rightarrow1$ + $4\Rightarrow2\rightarrow3\Rightarrow1$ + $4\Rightarrow2\rightarrow1$ + $4\Rightarrow2\Rightarrow1$ + $4\Rightarrow1$ **【数据范围】** **本题采用捆绑测试。** - Subtask 0(8 pts):$n\le20$。 - Subtask 1(11 pts):$n\le150$。 - Subtask 2(23 pts):$n\le300$。 - Subtask 3(26 pts):$n\le1000$。 - Subtask 4(32 pts):无特殊限制。 对于所有测试数据,$1\le n\le5\times10^3$,$2\le p\le 10^9+7$。
Samples
Input #1
3 1000000007
Output #1
3
Input #2
4 1000
Output #2
7
Input #3
100 511609
Output #3
272799
API Response (JSON)
{
  "problem": {
    "name": "【MX-S2-T3】 跳",
    "description": {
      "content": "给定一个坐标轴,范围是 $1\\sim n$。每个点 $i$ 可以跳到 $i+1$($i+1\\le n$)或 $i-1$($i-1\\ge 1$)或他的因子处。每个点只能到达一次。问从点 $n$ 到点 $1$ 一共有多少方案。答案对 $p$ 取模。 两种方案不同当且仅当存在一次跳跃后的位置不同或存在一次跳跃的种类不同。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10812"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个坐标轴,范围是 $1\\sim n$。每个点 $i$ 可以跳到 $i+1$($i+1\\le n$)或 $i-1$($i-1\\ge 1$)或他的因子处。每个点只能到达一次。问从点 $n$ 到点 $1$ 一共有多少方案。答案对 $p$ 取模。\n\n两种方案不同当且仅当存在一次跳跃后的位置不同或存在一次跳跃的种类不同。\n\n## Input\n\n一行两个整数 $n,p$。\n\n## Output\n\n一行一...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments