Description
The data scientists of CVTE declared that they had discovered a new number sequence system. The numbers sequences can be described as follows: they all have N numbers and their deferred expenses are A(i) = A(i-1) + x, where x equals a or b for different i. ( A(i) = 0 )
Now we are wondering that how many sequences satisfy that sigma( Ai ) 1 <= i <= n is between L and R.
Please module your final answer by 10^9 + 7.
Input
No more than 20000 test cases.The first line of each test case contains five number N, a, b, L and R. ( 2 <= N <= 100, -10000 <= a, b <= 10000, -10^9 <= L <= R <= 10^9 )
Output
Output your answer on a single line for each case.
Sample Input
5 1 2 0 15
Sample Output
1
这道题目出的水平还是有的，当时武大校赛时没做出来，，坑了队友，果然不训练真的是不行的。
题源：?problem_id=1579
题意：
A(i) = A(i-1) + a or b，求满足L <= ∑(Ai) <= R的有多少种。
思路：
相当于求(a or b) * n + (a or b) * (n – 1)…..(a or b) <= Rstep 1: 令c = b – a，那么相当于(c or 0) * n + (c or 0) * (n – 1) + ….(c or 0) <= R – a* n * (n + 1) / 2step 2：令X = R – a* n * (n + 1) / 2，相当于(1 or 0)* n + (1 or 0) * (n – 1)….(1 or 0) <= X / cstep 3：剩下一个简单dp计数问题，预处理即可。
至于a=b时，需要特判，我觉得序列都是一样的，但是出题人好像作为不同处理的 = =
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define mod 1000000007typedef long long ll;using namespace std;ll n,m;ll a,b,le,ri;ll dp[105][5055],sum[105][5055];ll getdp(ll x){if(x<0) return 0;if(x>=5050) x=5050;return sum[n][x];}int main(){ll i,j;dp[0][0]=1;for(i=0;i<100;i++){for(j=0;j<=i*(i+1)/2;j++){if(dp[i][j]==0) continue ;dp[i+1][j]+=dp[i][j];dp[i+1][j]%=mod;dp[i+1][j+(i+1)]+=dp[i][j];dp[i+1][j+(i+1)]%=mod;}}for(i=0;i<=100;i++){sum[i][0]=dp[i][0];for(j=1;j<=5050;j++){sum[i][j]=sum[i][j-1]+dp[i][j];sum[i][j]%=mod;}}while(~scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&le,&ri)){if(a==b){if((n+1)*n/2*a>=le&&(n+1)*n/2*a<=ri) printf("%lld\n",sum[n][n*(n+1)/2]);else printf("0\n");continue ;}if(a>b) swap(a,b);ll c=b-a;ll y;if((ri-a*n*(n+1)/2)<0) y=-1;else y=(ri-a*n*(n+1)/2)/c;ll x;if((le-a*n*(n+1)/2)<0) x=-1;else{if((le-a*n*(n+1)/2)%c==0) x=(le-a*n*(n+1)/2)/c-1;else x=(le-a*n*(n+1)/2)/c;}ll ans=getdp(y)-getdp(x);ans=(ans+mod)%mod;printf("%lld\n",ans);}return 0;}/*3 1 3 -7 63 1 3 0 15*/
也许这就是一个人无法抗拒的命运，有你、有我、也有他。
