波动数列

波动数列

观察这个数列:

$1$ $3$ $0$ $2$ $-1$ $1$ $-2$ …

这个数列中后一项总是比前一项增加 $2$ 或者减少 $3$,且每一项都为整数。

栋栋对这种数列很好奇,他想知道长度为 $n$ 和为 $s$ 而且后一项总是比前一项增加 $a$ 或者减少 $b$ 的整数数列可能有多少种呢?

输入格式

共一行,包含四个整数 $n,s,a,b$,含义如前面所述。

输出格式

共一行,包含一个整数,表示满足条件的方案数。

由于这个数很大,请输出方案数除以 $100000007$ 的余数。

数据范围

$1 \leq n \leq 1000$,
${−10}^{9} \leq s \leq {10}^{9}$,
$1 \leq a,b \leq {10}^{6}$

输入样例:

4 10 2 3

输出样例:

2

样例解释

两个满足条件的数列分别是$2$ $4$ $1$ $3$和$7$ $4$ $1$ $-2$。

 

解题思路

波动数列

  我们发现上面求和的等式右有很多的变量,其中$x \in Z$有无穷多种选法,每个$d_{i}$都有两种选法。因此每一个不同的$x$和每一组不同的$d_{i}$都对应一种不同的方案。

  我们可以发现这是一个等式,意味着可以去掉一个变量,即可以用其中的$n-1$个变量去表示某一个变量(一个很重要的思想,我经常想不到)。由于$x$可以取到很多值,所以我们可以用$d_{i}$来表示$x$。

  因此$x$可以表示为$$x = \frac{s - \left( \left( n-1 \right) \cdot d_{1} + \left( n-2 \right) \cdot d_{2} +......+ d_{n-1} \right)}{n}$$也就是说,当我们的$d_{i}$都确定后,$x$也是唯一确定的,是可以求出来的。

  因此任何一个合法的序列都对应一组$d_{i}$的取值,任何一组$d_{i}$的取值都可以对应一个原来的序列,因此这是一一对应的关系。因此原序列所有不同的方案数就等于所有$d_{i}$的合法取值的方案数。

  因此等价于求所有满足要求的$d_{i}$的取值的方案数。满足的要求有:$d_{i}$只有两种取值方式;由于$x$为整数,所以$$s - \left( \left( n-1 \right) \cdot d_{1} + \left( n-2 \right) \cdot d_{2} +......+ d_{n-1} \right)$$应该为$n$的倍数。等价于要满足$$s - \left( \left( n-1 \right) \cdot d_{1} + \left( n-2 \right) \cdot d_{2} +......+ d_{n-1} \right) \equiv 0 ~\left( mod~n \right)$$即$$\left( n-1 \right) \cdot d_{1} + \left( n-2 \right) \cdot d_{2} +......+ d_{n-1} \equiv s ~\left( mod~n \right)$$

  所以我们可以发现这是一个组合的问题,要求我们找到$d_{i}$的一个组合,满足$\left( n-1 \right) \cdot d_{1} + \left( n-2 \right) \cdot d_{2} +......+ d_{n-1} \equiv s ~\left( mod~n \right)$,类似于一个背包问题。

波动数列

  其中我们原本的式子为$\left( n-1 \right) \cdot d_{1} + \left( n-2 \right) \cdot d_{2} +......+ d_{n-1}$,我们可以变为$d_{1} + 2 \cdot d_{2} +......+ \left( n-1 \right) \cdot d_{n-1}$,因为每个$d_{i}$是等同的,每个$d_{i}$都是取$+a$或$-b$,因此改变变量名称是不影响的。其实不进行变换也是可以的,变化后处理会方便点。

  在状态计数中,最后一项是$+a$的所有方案这个集合中,对于前$i-1$项有$c + i \cdot a \equiv j ~\left( mod~n \right)$,因此有$c \equiv {j - \left( i \cdot a \right)} ~\left( mod~n \right)$。同理可得到对于最后一项是$-b$的所有方案这个集合中,有$c \equiv {j + i \cdot b} ~\left( mod~n \right)$。都可以从$f \left( {i-1,c} \right)$状态转移到$f \left( {i,j} \right)$。

  AC代码如下:

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int N = 1010, mod = 100000007;
 6 
 7 int f[N][N];
 8 
 9 int main() {
10     int n, s, a, b;
11     scanf("%d %d %d %d", &n, &s, &a, &b);
12     
13     f[0][0] = 1;    // 初始化:一项都不选,总和是0的情况
14     for (int i = 1; i < n; i++) {
15         for (int j = 0; j < n; j++) {
16             f[i][j] = (f[i - 1][((j - i * a) % n + n) % n] + f[i - 1][(j + i * b) % n]) % mod;
17         }
18     }
19     
20     printf("%d", f[n - 1][(s % n + n) % n]);
21     
22     return 0;
23 }

 

参考资料

  AcWing 1214. 波动数列(蓝桥杯C++ AB组辅导课):https://www.acwing.com/video/639/

上一篇:linux-awk-案例100例


下一篇:南阳理工oj88--汉诺塔(一)