常熟网站设计,哪个网站做logo,作风建设提升年活动网站,百度应用宝问题描述#xff1a; 观察如下数列#xff1a; 1 3 0 2 -1 1 -2 … 这个数列中后一项总是比前一项增加 2 或者减少 3。 栋栋对这种数列很好奇#xff0c;他想知道长度为 n nn 和为 s ss 而且后一项总是比前一项增加 a aa 或者减少 b bb 的整数数列可能有多少种呢#xff1f…问题描述 观察如下数列 1 3 0 2 -1 1 -2 … 这个数列中后一项总是比前一项增加 2 或者减少 3。 栋栋对这种数列很好奇他想知道长度为 n nn 和为 s ss 而且后一项总是比前一项增加 a aa 或者减少 b bb 的整数数列可能有多少种呢
输入格式 输入的第一行包含四个整数 n s a b n\ s\ a\ bn s a b含义如前面说述。
输出格式 输出一行包含一个整数表示满足条件的方案数。由于这个数很大请输出方案数除以 100000007 的余数。
样例输入 4 10 2 3
样例输出 2
样例说明 这两个数列分别是 {2 4 1 3} 和 {7 4 1 -2}。
暴力解法超时
#includeiostream
#includestring
#includecmath
using namespace std;
#define base 100000007
int n,s,a,b;
long long sum0;
void check(int k)
{double changes-k;double firstchange/n;if(fmod(first,1)0){//计算出的第一个数为整数sum;sum%base;}
}
void calculate(int,int);int main()
{cinnsab;calculate(n-1,0);coutsum;return 0;
}
void calculate(int layer,int u)
{//递归出口if(layer0){check(u);return;}int additionlayer*a;calculate(layer-1,uaddition);addition(-b)*layer;calculate(layer-1,uaddition);
}动态规划
#includeiostream
#includestring
#includecmath
using namespace std;
#define base 100000007
long long a,b,n,s;
const int N1000010;
int f[N]{0};
//f[i][j]表示从1~n-1中前i个数中选择使得和为j的种类数
//f[i][j]f[i-1][j]f[i-1][j-i]; f[i][0]1;
void create()
{//参考01背包问题f[0]1;for(int i1;in-1;i){int numi*(i1)/2;for(int jnum;ji;j--){//需要倒序使得f[j-1]为f[i-1][j-1];f[j](f[j]f[j-i])%base;}}
}void calculate();int main()
{cinnsab;create();calculate();return 0;
}
void calculate()
{int numn*(n-1)/2;long long sum0;for(int i0;inum;i){long long ui*a-(num-i)*b;long long temps-u;if(temp%n0){//n-1个位置取i个位置sum(sumf[i])%base;}}coutsum;
}
