波动数列
观察这个数列:
$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/