问题描述

　　观察这个数列：

　　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。

 解题思路：

ps：我用的是网上普遍的dp方法，但是后台数据只能通过90%，提交网上一些大佬的代码也是只能通过90%，另一个样例始终超时。

 

dp思路：也是看着大佬的博客一步步弄清的。（http://blog.csdn.net/wr132/article/details/43861145）

 

但是我觉得还是有些地方晦涩了点，所以自己瞎写了一通。

1、首先我们将每个+a和-b操作都当做操作p，所以易知

设首项为x，可以得到一个等式x+(x+P)+(x+2P)+...+(x+(n-1)P)=s，将这个式子整理一下，就是

nx+P+2P+...+(n-1)P=s

，即(s-(P+2P+...+(n-1)P))/n=x。

 

2、所以我们确定了a操作的次数就知道了b操作的次数。于是我们记前 i 个元素所进行的a操作数 j 所能够组成的方案数为dp[ n ] [n*(n-1) /2 ]。即数组大小为dp[ n ] [n*(n-1) /2 ]。

（空间复杂度咱先不管，后面处理，先搞出思路来）

 

3、初始化dp数组，显然当 i !=0，j=0时，dp[ i ] [ 0] =1;当 i =0时 ，dp [ 0] [ j ]=0；

 

4、初始化好了，状态转移方程为

(1)、i>j时，因为每一个元素i权值都是i，即dp[i][j]=dp[i-1][j]。（ps：个人理解也不是很透，可能这就是dp的妙处吧）

(2)、i<=j时，第i个元素的权值是小于等于和的，所以可以用，也可以不用，如果不用，那么就是dp[i-1][j]，如果用，就是dp[i-1][j-i]，这个有点类似于01背包，所以

dp[i][j]=dp[i-1][j]+dp[i-1][j-i]。

 

5、显然不可能开dp[n][n*n]的数组，于是我们进行内存压缩！！！ 这就是last变量存在的意义！！！

 

代码：

1 #include
       
         2 #include
        
          3 #define ll long long 4 using namespace std; 5 const ll MOD=100000007; 6 ll n,s,a,b; 7 ll dp[2][1060*1060]; 8 ll last=0; 9 void get_dp(){10     memset(dp,0,sizeof(dp));11     dp[0][0]=1;12     for(ll i=1;i
         
          j){16                 dp[last][j]=dp[1-last][j];17             }else{18                 dp[last][j]=(dp[1-last][j-i]+dp[1-last][j])%MOD;19             }20         }21     }22 }23 int main(){24     cin>>n>>s>>a>>b;25     get_dp();26     ll cnt=0;27     for(ll i=0;i<=n*(n-1)/2;i++){28         ll tmp=s-a*i+(n*(n-1)/2-i)*b;29         if(tmp%n==0){30             cnt=(cnt+dp[last][i])%MOD;31         }32     }33     cout<
          
           <