环球快看点丨波动数列

2023-03-20 20:00:56 来源：博客园

波动数列

[蓝桥杯 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 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$

代码：

#includetypedef 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++)//由于j是对n取模后的结果，则j的范围是[0, n-1]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)]);return 0;}

关键词：