题目描述

观察这个数列：

1 3 0 2 -1 1 -2 …

这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。

栋栋对这种数列很好奇，他想知道长度为 n
和为 s
而且后一项总是比前一项增加 a
或者减少 b
的整数数列可能有多少种呢？

输入格式

共一行，包含四个整数 n,s,a,b
，含义如前面所述。

输出格式

共一行，包含一个整数，表示满足条件的方案数。

由于这个数很大，请输出方案数除以 100000007
的余数。

数据范围

1≤n≤1000,
−109≤s≤109,
1≤a,b≤106

输入样例：

4 10 2 3

输出样例：

2

样例解释

两个满足条件的数列分别是2 4 1 3和7 4 1 -2。

分析

设第一个数为x，则第二个数为x+d1，第三个数为x+d1+d2+…。这里的d1，d2表示a或者−b，所以这个数列为：

状态表示：设 f[i][j] 为选了i个数，前 i 个 d 的和模 n 的余数为 j 的集合的数量

明确目标：最后求得是 f[n−1][s%n] 的值

算法 数学+动态规划DP

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;
const int N=1010;
int f[N][N];
int n,s,a,b;
int Mod=100000007;

int get_Mod(int a,int b){  //防止c++中算出的余数为负数，因为数学中余数是不能为负的
    return (a%b+b)%b;
}
int main(){
    cin>>n>>s>>a>>b;
    f[0][0]=1;   //而初始化边界条件dp[0][0]代表选0个a或者b且余数也为0,就代表只有唯一的方案。
    for(int i=1;i<n;i++){
        for(int j=0;j<n;j++){  //余数可以是任意整数
            f[i][j]=(f[i-1][get_Mod(j-(n-i)*a,n)]+f[i-1][get_Mod(j+(n-i)*b,n)])%Mod;
        }
    }
    cout<<f[n-1][get_Mod(s,n)]<<endl;
    return 0;
}