算法1

思路：这是一道动态规划题目
1.初步分析
首先，初值范围未知，只知道是一个整数
可以设数列首项为x, 第i次操作为pi(pi属于{+a, -b});
则数列为: x, x+p1, x+p1+p2, ......, x+p1+p2+…+p(n-1)

2.问题转化
数列的和为: nx+(n-1)p1+(n-2)p2+…+p(n-1) = s
即: x = {s - [(n-1)p1+(n-2)p2+…+p(n-1)] }/n
x为整数，故 {s - [(n-1)p1+(n-2)p2+…+p(n-1)] }%n = 0
即s 与 [(n-1)p1+(n-2)*p2+…+p(n-1)] 模n同余,共n-1项的和

3.寻找转移方程
这样通过模n将每种状态的数据范围限制在n以内，可以用动态规划解决
所以可以用f[i][j]表示前i项数列组成的和si%n为j时的方案数
而f[i][j] 可以由f[i-1][(j-a(n-i))%n]和f[i-1][(j+b(n-i))%n]转移过来
(a和b后面都需要+-(n-i)次，所以要乘上(n-i)

故f[i][j] = f[i-1][(j-a(n-i))%n]+f[i-1][(j+b(n-i))%n]
(注意：c++%运算有可能出现负数结果，需要自定义非负的取余运算)

4.确定初值和答案
因为未进行任何操作时数列只有0项，和为0，初始时只有这样一个合法状态，故f[0][0] = 1;
目标状态：合法转移到s，共有n-1步，故最终答案为f[n-1][s%n]

作者：macat
链接：https://www.acwing.com/solution/content/19121/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

C++ 代码

#include <iostream>

using namespace std;

const int N = 1010, base = 1e8+7;
int n, s, a, b;
int f[N][N];
//非负取模运算,%n
int mod(int x) {
    return (x%n+n)%n;
}

int main() {
    cin>>n>>s>>a>>b;
    f[0][0] = 1;
    for(int i = 1; i < n; ++i) {//枚举i-1项
        for(int j = 0; j < n; ++j) {//枚举第i项的n种可能的状态
            f[i][j] = (f[i-1][mod(j-a*(n-i))]+f[i-1][mod(j+b*(n-i))])%base;
        }
    }
    cout<<f[n-1][mod(s)];
    return 0;
}