题目链接 蓝桥杯---历届真题 题解
问题描述
观察这个数列： 1 3 0 2 -1 1 -2 ... 这个数列中后一项总是比前一项增加2或者减少3。 栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢？
分析：设操作P(+a,-b),则数列每个项为 x x+P x+2P x+3P ... X+(n-1)P,则P操作一共有sumP = n*(n-1)/2次。设+a，-b的次数为cnta，cntb,那么cnta +cntb = sumP。那么我们只需要确定其中一个cnta就能得到cntb。用d[i][j]表示前i个数列进行j次+a操作的次数和；则d[i][j] = d[i][j] + d[i][j-i];（//第i个数要么+a,要么不加a），因为空间不够二维数组，可以用滑动数组降为一位数组（和01背包一样）。因为s = n*x + cnta*b - (n*(n-1)/2 - cnta)*b;那么最后我们只需要枚举cnta的次数看x是否有整数解存在，每次加上d[i]即可。
#include <iostream> using namespace std; typedef long long LL; const LL MAXN = 1000, MOD = 100000007; LL d[MAXN*MAXN]; int main(int argc, char** argv) { LL n, s, a, b; cin>> n >> s >> a >> b; d[0] = 1; for(LL i = 1; i < n; i++) for(LL j = i*(i+1)/2; j >= i; j--) d[j] = (d[j] + d[j-i]) % MOD; LL ans = 0; for(LL i = 0; i <= n*(n-1)/2; i++){ LL t = s + i*a - (n*(n-1)/2-i)*b; if(t % n == 0) ans = (ans + d[i]) % MOD; } cout<< ans << "\n"; return 0; }输入格式
输入的第一行包含四个整数 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。
