本文共 1276 字，大约阅读时间需要 4 分钟。

波动数列     观察这个数列：     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。 资源约定： 峰值内存消耗 < 256M CPU消耗  < 1000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。 注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

#include
   
    #include
    
     //这个头文件有意思 #define Max 1100#define MOD 100000007using namespace std;int F[2][Max*Max];int e=0;long long n,s,a,b;int count=0;void DP(int elem){	int i,j;	memset(F,0,sizeof(F));	F[e][0]=1;	for(i=1;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;   DP(n*(n-1)/2);   for(int i=0;i<=n*(n-1)/2;i++)   {	    t=s-i*a+(n*(n-1)/2-i)*b;	    if(t%n==0)	    count=(count+F[e][i])%MOD;   } 	cout<
      
       <
      
     
    
   

转载地址：https://blog.csdn.net/weixin_38960774/article/details/79424599 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！