欢迎关注

分析

基本思路：
首先这是一道动态规划题目，但一开始就想到的是搜索，所以就各种搜索剪枝，实际上都是徒劳。
像这种简单的DP题目一般都有两个特点：

• 长得和搜索题很像，甚至就能用搜索做

• 有一个大的吓人的数据

看清这两点，明确了思路，下面开始进入分析阶段：

1. 按照题目要求，最终得到的序列的长度为$n$，和为$s$，并且后一项是前一项加$a$或$-b$，我们不妨将这个操作封装在一起，记作$P$操作，即$P=(a,-b)$。
2. 设首项为x，可以得到一个等式$x+(x+P)+(x+2P)+…+(x+(n-1)P)=s$，将这个式子整理一下，就是$nx+P+2P+…+(n-1)P=s$，即$(s-(P+2P+…+(n-1)P))/n=x$。
3. 我们不妨将最后一次操作拿出来单独考虑，最后一次操作要么是+a，要么是-b。我们设$f[i][j]$表示只考虑前$i$ 项，且当前的总和除以$n$的余数是$j$的方案的集合, 那么状态转移方程就可以是$f[i][j]=f[i - 1][j - a * i] + f[i - 1][j + b * i]$

C++ 代码

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1005, MOD = 100000007;

int f[N][N];

int get_mod(int a, int b)
{
    return (a % b + b) % b;
}

int main()
{
    int n, s, a, b;
    cin >> n >> s >> a >> b;

    f[0][0] = 1;

    for (int i = 1; i <= n - 1; i++)
    {
        for (int j = 0; j <= n - 1; j++)
        {
            f[i][j] = (f[i - 1][get_mod(j - a * i, n)] + f[i - 1][get_mod(j + b * i, n)]) % MOD;
        }
    }

    cout << f[n - 1][s % n] << endl;

    return 0;
}