题目大意
求满足和为 s s s 且 t i = t i − 1 + a t_i=t_{i-1}+a ti=ti−1+a 或 t i = t i − 1 − b t_i=t_{i-1}-b ti=ti−1−b 的长度为 n n n 的数列 t t t 的方案数。
思路
首先，得确定大概方向：
一提到方案数，你会想到什么？
-
搜索（当然可以，只是会 T 到飞起）
-
记忆化搜索（emmm，我暂时还没研究过，或许可以吧）
-
大炮——dp！（此题正解）
其次，冷静分析数据范围：
看到题目里面的 n ≤ 1000 n \leq 1000 n≤1000，再看看空间范围就可以大概猜测：用 O ( n 2 ) O(n^2) O(n2) 的时空复杂度。这就是本题最清晰的解法。
然后，设计状态：
我们发现只有 n n n 这一个变量可以二重循环，因此，我们尝试进行每重循环的次数都和 n n n 有关。但是即使这样，空间也有可能不够啊！后面的都是 1 0 6 10^6 106 级以上的！怎么办？我们会想到取模。于是设 d p i , j dp_{i, j} dpi,j 表示前 i i i 项的和模 n n n 等于 j j j 时的方案数。
最后，最重要的转移方程：
关于取模的转移方程，我不细讲了，就看 RoMantic_Queue 大佬的吧。觉得他讲的详细些。
在一些数学推导（其实这题也是个数学题）后，得到转移方程 d p [ i ] [ j ] = ( d p [ i − 1 ] [ c ( j − a × i ) ] + d p [ i − 1 ] [ c ( j + b × i ) ] ) dp[i][j]=(dp[i-1][c(j-a×i)] + dp[i-1][c(j+b×i)]) dp[i][j]=(dp[i−1][c(j−a×i)]+dp[i−1][c(j+b×i)])，其中 c ( x ) c(x) c(x) 表示 x x x 对 n n n 取模的结果，注意负数。
坑点：
-
注意模数是 1 0 8 + 7 10^8 + 7 108+7。
-
注意转移方程里面的加减，别搞混了。
代码奉上：
//time：2023-04-01
#include <bits/stdc++.h>
using namespace std;
#define mod 100000007
typedef long long ll;
int n, s, a, b;
int dp[1007][1007];
inline int c(int x) {
return (x % n + n) % n;
}
int main() {
cin >> n >> s >> a >> b;
dp[0][0] = 1;
for(int i = 1; i < n; i++)
for(int j = 0; j < n; j++)
dp[i][j] = (dp[i - 1][c(j - a * i)] + dp[i - 1][c(j + b * i)]) % mod;
cout << dp[n - 1][c(s)];
return 0;
}