[蓝桥杯 2014 省 A] 波动数列

Luogu
IDLGP8614
Time1000ms
Memory128MB
DifficultyP3
动态规划 DP2014蓝桥杯省赛
观察这个数列: $1,3,0,2,-1,1,-2, \cdots $。 这个数列中后一项总是比前一项增加 $2$ 或者减少 $3$。 栋栋对这种数列很好奇,他想知道长度为 $n$ 和为 $s$ 而且后一项总是比前一项增加 $a$ 或者减少 $b$ 的整数数列可能有多少种呢? ## Input 输入的第一行包含四个整数 $n,s,a,b$,含义如前面说述。 ## Output 输出一行,包含一个整数,表示满足条件的方案数。由于这个数很大,请输出方案数除以 $100000007$ 的余数。 [samples] ## Note 【样例说明】 这两个数列分别是 2 4 1 3 和 7 4 1 -2。 【数据规模与约定】 对于 $10\%$ 的数据,$1 \le n \le 5$,$0 \le s \le 5$,$1 \le a,b \le 5$; 对于 $30\%$ 的数据,$1 \le n \le 30$,$0 \le s \le 30$,$1 \le a,b \le 30$; 对于 $50\%$ 的数据,$1 \le n \le 50$,$0 \le s \le 50$,$1 \le a,b \le 50$; 对于 $70\%$ 的数据,$1 \le n \le 100$,$0 \le s \le 500$,$1 \le a,b \le 50$; 对于 $100\%$ 的数据,$1 \le n \le 1000$,$-10^9 \le s \le 10^9$,$1 \le a,b \le 10^6$。 时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛
Samples
Input #1
4 10 2 3
Output #1
2
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2014 省 A] 波动数列",
    "description": {
      "content": "观察这个数列: $1,3,0,2,-1,1,-2, \\cdots $。 这个数列中后一项总是比前一项增加 $2$ 或者减少 $3$。 栋栋对这种数列很好奇,他想知道长度为 $n$ 和为 $s$ 而且后一项总是比前一项增加 $a$ 或者减少 $b$ 的整数数列可能有多少种呢?",
      "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": "LGP8614"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "观察这个数列:\n\n$1,3,0,2,-1,1,-2, \\cdots $。\n\n这个数列中后一项总是比前一项增加 $2$ 或者减少 $3$。\n\n栋栋对这种数列很好奇,他想知道长度为 $n$ 和为 $s$ 而且后一项总是比前一项增加 $a$ 或者减少 $b$ 的整数数列可能有多少种呢?\n\n## Input\n\n输入的第一行包含四个整数 $n,s,a,b$,含义如前面说述。\n\n## Output\n\n输出一行...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments