1214. 波动数列
摘要
Title: 1214. 波动数列
Tag: dp
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1214. 波动数列
-
题意
观察这个数列：
1 3 0 2 -1 1 -2 …
这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。
栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢？ -
思路
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20'''
Author: NEFU AB-IN
Date: 2022-03-24 11:41:45
FilePath: \ACM\Acwing\1214.py
LastEditTime: 2022-03-24 11:41:46
'''
MOD = 100000007
N = 1010
dp = [[0] * N for _ in range(N)]
n, s, a, b = map(int, input().split())
dp[0][0] = 1
for i in range(1, n + 1):
for j in range(0, n):
dp[i][j] = (dp[i][j] + dp[i - 1][(j - a * i) % n]) % MOD
dp[i][j] = (dp[i][j] + dp[i - 1][(j + b * i) % n]) % MOD
print(dp[n - 1][s % n])
