[蓝桥杯 2020 省 AB3] 画中漂流

Luogu
IDLGP8725
Time1000ms
Memory128MB
DifficultyP3
动态规划 DP2020容斥原理蓝桥杯省赛
在梦境中,你踏上了一只木䇝,在江上漂流。 根据对当地的了解,你知道在你下游 $D$ 米处有一个峡谷,如果你向下游前进大于等于 $D$ 米则必死无疑。 现在你打响了急救电话,$T$ 秒后救援队会到达并将你救上岸。水流速度是 $1 \mathrm{~m} / \mathrm{s}$,你现在有 $M$ 点体力。每消耗一点体力,你可以划一秒桨使船向上游前 进 $1 \mathrm{~m}$,否则会向下游前进 $1 \mathrm{~m}$ (水流)。$M$ 点体力需在救援队赶来前花光。因为江面太宽了,凭借你自己的力量不可能上岸。 请问,有多少种划桨的方案可以让你得救。 两个划桨方案不同是指:存在某一秒钟,一个方案划桨,另一个方案不划。 ## Input 输入一行包含三个整数 $D$,$T$,$M$。 ## Output 输出一个整数,表示可以让你得救的总方案数,答案可能很大,请输出方案数除以 $1000000007$(即 $10^9+7$)的余数。 [samples] ## Note 对于 $50 \%$ 的评测用例,$1 \leq T \leq 350$。 对于所有评测用例,$1 \leq T \leq 3000,1 \leq D \leq T,1 \leq M \leq 1500$。 蓝桥杯 2020 第三轮省赛 AB 组 I 题。
Samples
Input #1
1 6 3
Output #1
5
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2020 省 AB3] 画中漂流",
    "description": {
      "content": "在梦境中,你踏上了一只木䇝,在江上漂流。 根据对当地的了解,你知道在你下游 $D$ 米处有一个峡谷,如果你向下游前进大于等于 $D$ 米则必死无疑。 现在你打响了急救电话,$T$ 秒后救援队会到达并将你救上岸。水流速度是 $1 \\mathrm{~m} / \\mathrm{s}$,你现在有 $M$ 点体力。每消耗一点体力,你可以划一秒桨使船向上游前 进 $1 \\mathrm{~m}$,否则会向下",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8725"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在梦境中,你踏上了一只木䇝,在江上漂流。\n\n根据对当地的了解,你知道在你下游 $D$ 米处有一个峡谷,如果你向下游前进大于等于 $D$ 米则必死无疑。\n\n现在你打响了急救电话,$T$ 秒后救援队会到达并将你救上岸。水流速度是 $1 \\mathrm{~m} / \\mathrm{s}$,你现在有 $M$ 点体力。每消耗一点体力,你可以划一秒桨使船向上游前 进 $1 \\mathrm{~m}$,否则会向下...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments