[蓝桥杯 2014 省 A] 波动数列
题目描述
观察这个数列：
$1,3,0,2,-1,1,-2, \cdots $。
这个数列中后一项总是比前一项增加 \(2\) 或者减少 \(3\)。
栋栋对这种数列很好奇，他想知道长度为 \(n\) 和为 \(s\) 而且后一项总是比前一项增加 \(a\) 或者减少 \(b\) 的整数数列可能有多少种呢？
输入格式
输入的第一行包含四个整数 \(n,s,a,b\)，含义如前面说述。
输出格式
输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以 \(100000007\) 的余数。
样例 #1
样例输入 #1
4 10 2 3
样例输出 #1
2
提示
【样例说明】
这两个数列分别是 2 4 1 3 和 7 4 1 -2。
【数据规模与约定】
对于 \(10\%\) 的数据，\(1 \le n \le 5\)，\(0 \le s \le 5\)，\(1 \le a,b \le 5\)；
对于 \(30\%\) 的数据，\(1 \le n \le 30\)，\(0 \le s \le 30\)，\(1 \le a,b \le 30\)；
对于 \(50\%\) 的数据，\(1 \le n \le 50\)，\(0 \le s \le 50\)，\(1 \le a,b \le 50\)；
对于 \(70\%\) 的数据，\(1 \le n \le 100\)，\(0 \le s \le 500\)，\(1 \le a,b \le 50\)；
对于 \(100\%\) 的数据，\(1 \le n \le 1000\)，\(-10^9 \le s \le 10^9\)，\(1 \le a,b \le 10^6\)。
题解
不妨设数列首项为\(a_1\),操作数为\(x\)，其中\(x = a\) \(or\) \(x = -b\)，易知\(s=\sum_1 ^n a_1+(i-1)x\)， 即$$s=na_1+\frac{n(n-1)}{2}x$$由于\(n, a, b, s\)都是整数，且波动数列为整数数列，则 \(a_1 \in Z\)，记 \(z = \frac{n(n-1)}{2}x\)，则 \(a_1=\frac{s-z}{n}\)，即 \(s\) mod \(n\) = \(z\) mod \(n\). 题目中已给定\(s、n\)的值，那么题意转化为有多少种方案能使得 \(z\) 与 \(s\) 模 \(n\) 同余，并满足数列长度为 \(n\) 项且和为 \(s\). 设 \(dp_{i,j}\) 表示 \(z\) 的前 \(i\) 项的序列和模 \(n\) 后值为 \(j\) 的方案数。
- \(z\) 的前 \(i\) 项序列和，即 \(x * (0 + 1 + 2 + ... + i)\) (注：事实上 \(0 + 1 + ... + i\) 不能写成求和的形式，因为 \(x\) 并不是一个确定的自然数，对于某一项我们取\(a\)还是取\(b\)是不一定的，上文推导中记作求和仅仅是为了方便)
- 前 \(i\) 项序列和模 \(n\) 为 \(j\)，即 \(j=[a_1 + (a_1 + x) + (a_1 + 2x) + ... + (a_1 + (i-1)x)]\) mod \(n\)。
因为\(x = a\) \(or\) \(x = -b\)，那么第 \(i\) 项将由第 \(i-1\) 项推出，即状态转移方程为：$$dp_{i,j}=dp_{i-1,Mod(j-i·a)} + dp_{i-1,Mod(j+i·b)}$$
- \(Mod (x) =\) ( \(x\) mod \(n + n\) ) mod \(n\). 这样能够保证余数是个正数.
- \((a \pm b)\) mod \(n\) = ( \(a\) mod \(n\) \(\pm\) \(b\) mod \(n\) ) mod \(n\)
- 初始值\(dp_{0,0}=1\)
代码：
#include<cstdio>
typedef long long LL;
const LL N=1e3+3, mod=1e8+7;
LL n,dp[N][N];
int Mod(LL x){return (x%n+n)%n;}
int main(){
LL s,a,b;
scanf("%lld%lld%lld%lld",&n,&s,&a,&b);
dp[0][0]=1;
for(LL i=1;i < n; i++)
for(LL j=0;j < n; j++)
dp[i][j]=(dp[i-1][Mod(j-a*i)]+dp[i-1][Mod(j+b*i)])%mod;
printf("%lld",dp[n-1][Mod(s)]);
}