题目分析

1.初步分析

首先，初值范围未知，只知道是一个整数
可以设数列首项为$x$, 第$i$次操作为$p_i(p_i属于{+a, -b})$;
则数列为: $x, x+p_1, x+p_1+p_2, ......, x+p_1+p_2+…+p_{n-1}$

2.问题转化

数列的和为:
$n \* x + (n-1)\*p_1 + (n-2) \* p_2+…+ p_{n-1}=s$

即:$x = [s - [(n-1)\*p_1+(n-2)\*p_2+…+p_{n-1}] ]/n$
$x$为整数，故 $[s - [(n-1)\*p_1+(n-2)\*p_2+…+p_{n-1}] ]\%n = 0$
即$s$ 与 $[(n-1)\*p_1+(n-2)\*p_2+…+p_{n-1}]$模$n$同余,共$n-1$项的和

3.寻找转移方程

这样通过模$n$将每种状态的数据范围限制在$n$以内，可以用动态规划解决
所以可以用$f[i][j]$表示前$i$项数列组成的和$s_i%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]$

时间复杂度：$O(n^2)$

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;
}