solution.md

# 波动数列

**问题描述**

观察这个数列：  
1 3 0 2 -1 1 -2 ...  
这个数列中后一项总是比前一项增加2或者减少3。  
栋栋对这种数列很好奇，他想知道长度为 ```n``` 和为 ```s``` 而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢？  

**输入格式**

　　输入的第一行包含四个整数``` n s a b```，含义如前面说述。

**输出格式**

　　输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以100000007的余数。

**样例输入**

```4 10 2 3```

**样例输出**

```2```

**样例说明**

这两个数列分别是```2 4 1 3```和```7 4 1 -2```。

**数据规模和约定**

对于10%的数据，1<=n<=5，0<=s<=5，1<=a,b<=5；  
对于30%的数据，1<=n<=30，0<=s<=30，1<=a,b<=30；  
对于50%的数据，1<=n<=50，0<=s<=50，1<=a,b<=50；  
对于70%的数据，1<=n<=100，0<=s<=500，1<=a, b<=50；  
对于100%的数据，1<=n<=1000，-1,000,000,000<=s<=1,000,000,000，1<=a, b<=1,000,000。  

以下错误的一项是？

## aop
### before
```cpp

```
### after
```cpp

```

## 答案
```cpp
long long n, s, a, b;
long long sum;
long long cnt = 0;
long long mo = 100000007;
int dfs(long long nn, long long rn)
{

    sum += nn;
    if (rn == 0)
    {

        if (sum == s)
        {
            sum -= nn;

            cnt++;
            cnt %= mo;
            return 1;
        }
        else
        {
            sum -= nn;
            return 0;
        }
    }
    dfs(nn + a, rn - 1);
    dfs(nn + b, rn - 1);
    sum -= nn;
}
int main(void)
{
    cin >> n >> s >> a >> b;

    for (long long i = s - n * a; i < s + n * b; i++)
    {
        sum = 0;
        dfs(i, n - 1);
    }
    cout << cnt << endl;
    return 0;
}
```
## 选项

### A
```cpp
#define MAXN 1100
#define MOD 100000007
using namespace std;

int F[2][MAXN * MAXN];
int e = 0;
long long n, s, a, b;
int cnt = 0;

void calc(int elem)
{
    int i, j;
    memset(F, 0, sizeof(F));
    F[e][0] = 1;
    for (i = 1; i < n; i++)
    {
        e = 1 - e;
        for (j = 0; j <= i * (i + 1) / 2; j++)
        {
            if (i > j)
                F[e][j] = F[1 - e][j];
            else
                F[e][j] = (F[1 - e][j] + F[1 - e][j - i]) % MOD;
        }
    }
}

int main()
{

    cin >> n >> s >> a >> b;
    long long i, t;
    calc(n * (n - 1) / 2);
    for (i = 0; i <= n * (n - 1) / 2; i++)
    {
        t = s - i * a + (n * (n - 1) / 2 - i) * b;
        if (t % n == 0)
            cnt = (cnt + F[e][i]) % MOD;
    }
    printf("%d", cnt);
    return 0;
}
```

### B
```cpp
int n, s, a, b;
int num;

void dfn(int cur, int all, int id)
{
    if (id == n)
    {
        if (all == s)
        {
            num++;
            num = num % 100000007;
            return;
        }
        else
        {
            return;
        }
    }
    dfn(cur + a, all + cur + a, id + 1);
    dfn(cur - b, all + cur - b, id + 1);
}
int main()
{
    long long i, total;
    cin >> n >> s >> a >> b;
    total = s + n * b;
    for (i = s - n * a; i <= total; i++)
    {
        dfn(i, i, 1);
    }
    cout << num;
    return 0;
}
```

### C
```cpp
const int MAXN = 1050;
typedef long long ll;

const int mod = 100000007;
int main()
{
    ll n, s, a, b;

    scanf("%lld%lld%lld%lld", &n, &s, &a, &b);

    int T = n * (n - 1) / 2;
    int dp[2][T + 1];
    memset(dp, 0, sizeof(dp));

    int *crt = dp[0];
    int *next = dp[1];
    crt[0] = 1;
    next[0] = 1;

    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j <= (i + 1) * i / 2; j++)
        {
            if (j < i)
                next[j] = crt[j] % mod;

            else
                next[j] = (crt[j] + crt[j - i]) % mod;
        }
        swap(crt, next);
    }
    ll ans = 0;
    for (ll ta = 0; ta <= T; ta++)
    {
        ll num = s + (T - ta) * b - ta * a;
        if (num % n == 0)
        {

            ans = (ans + crt[ta]) % mod;
        }
    }

    cout << ans;
    return 0;
}
```