蓝桥 PREV-30历届试题 波动数列【动态规划】

  历届试题 波动数列   时间限制：1.0s   内存限制：256.0MB      问题描述 　　观察这个数列： 　　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。

题目链接：

　　http://lx.lanqiao.cn/problem.page?gpid=T122

题目大意：

　　一个数列长度为n，每一项等于前一项+a或者-b，数列和为s，求数列的个数 mod 100000007。

题目思路：

　　【动态规划】

　　首先考虑如果全+a，数列和则会+a*(n-1)n/2，-b同理

　　即对于和s来说总共有(n-1)n/2次+或-操作。于是考虑如何将(n-1)n/2次操作分配给+a和-b。

　　容易想到这就是一个DP问题  f[i][j]表示前i个数，+a了j次的方案数。

　　第i个+a: f[i-1][j-i]， 第i个-b: f[i-1][j]

　　最后枚举+a的个数为i的情况下，将数列和s补到+a-b之前的状态，看是否满足%n=0(即求首项为整数)

　　可行则答案加上当前的分配方案数。

　　f[i][j]可以化成1维

/**************************************************** Author : Coolxxx Copyright 2017 by Coolxxx. All rights reserved. BLOG : http://blog.csdn.net/u010568270 ****************************************************/ #include<bits/stdc++.h> #pragma comment(linker,"/STACK:1024000000,1024000000") #define abs(a) ((a)>0?(a):(-(a))) #define lowbit(a) (a&(-a)) #define sqr(a) ((a)*(a)) #define mem(a,b) memset(a,b,sizeof(a)) const double eps=1e-8; const int J=10000; const int MOD=100000007; const int MAX=0x7f7f7f7f; const double PI=3.14159265358979323; const int N=1004; using namespace std; typedef long long LL; double anss; LL aans; int cas,cass; int n,m,lll,ans; LL s,a,b; LL f[N*N]; int main() { #ifndef ONLINE_JUDGE // freopen("1.txt","r",stdin); // freopen("2.txt","w",stdout); #endif int i,j,k,l; int x,y,z; // for(scanf("%d",&cass);cass;cass--) // for(scanf("%d",&cas),cass=1;cass<=cas;cass++) // while(~scanf("%s",s)) while(~scanf("%d",&n)) { mem(f,0); cin>>s>>a>>b; f[0]=1;aans=0; for(i=1;i<n;i++) for(j=i*(i+1)/2;j>=i;j--) f[j]=(f[j]+f[j-i])%MOD; for(i=0;i<=n*(n-1)/2;i++) { LL t=s-i*a+((n-1)*n/2-i)*b; if(t%n==0)aans=(aans+f[i])%MOD; } cout<<aans<<endl; } return 0; } /* // // */