题目描述
观察这个数列:
$$ 1, 3, 0, 2, -1, 1, -2, … $$
这个数列中后一项总是比前一项增加 $2$ 或者减少 $3$,且每一项都为整数。
栋栋对这种数列很好奇,他想知道长度为 $n$ 和为 $s$ 而且后一项总是比前一项增加 $a$ 或者减少 $b$ 的整数数列可能有多少种呢?
输入格式
共一行,包含四个整数 $n,s,a,b$,含义如前面所述。
输出格式
共一行,包含一个整数,表示满足条件的方案数。
由于这个数很大,请输出方案数除以 $100000007$ 的余数。
数据范围
$$ 1≤n≤1000, −10^9≤s≤10^9, 1≤a,b≤106 $$
输入样例:
4 10 2 3
输出样例:
2
算法1
(动态规划) $O(n^2)$
首先假设序列的第一个元素为 $x$, 则整个序列就变为
$$
x, x + d_{1}, x + d_{1} + d_{2}, \cdots, x + d_{1} + d_{2} + \cdots + d_{n - 1}
$$
其中 $d_{i} = \{a, -b\} $. 满足要求也就是下述等式成立.
$$
nx + (n - 1) d_{1} + (n - 2)d_{2} + \cdots + d_{n - 1} = s.
$$
也就是要求
$$
s = (n - 1) d_{1} + (n - 2)d_{2} + \cdots + d_{n - 1}(mod~~ n)
$$
满足上述条件的序列就是一个合法方案.
- 状态表示: $f(i, j)$ 表示选取 $i$ 个数, 第 $i$ 个数为 $ai$ 或 $-bi$, 它们的和余数为 $j$ 的方案数.
- 状态计算:根据最后一个数的选取可以将方案划分为两部分
$f(i, j) = (f(i - 1, mod(j - ai, n)) + f(i - 1, mod(j + bi, n)))mod 100000007$. - 初始状态: $f(0,0) = 1$
参考文献
y 总视频
C++ 代码
#include<iostream>
using namespace std;
const int N = 1010, P = 1e8 + 7;
int n, s, a, b;
int f[N][N];
int mod(int x, int n) {
return (x % n + n) % n;
}
int main(){
cin >> n >> s >> a >> b;
f[0][0] = 1;
for (int i = 1; i < n; ++ i)
for (int j = 0; j < n; ++ j)
f[i][j] = (f[i - 1][mod(j - a * i, n)] + f[i - 1][mod(j + b * i, n)]) % P;
cout << f[n - 1][mod(s, n)] << endl;
return 0;
}