1214. 波动数列(推公式 + DP)

题目如下：

思路 or 题解：

我们可以设： 第一个数为 $x$
d = {a, -b}
那后续的数为：$x+d_1$ , $x+d_1+d_{)}2$ … … $x+d_1+d_2+......+d_{n-1}$
根据题意和上面的式子
我们合并一下同类项：
$n\ast x+(n-1)\ast d_1+(n-2)\ast d_2+......+d_{n-1}=s$
我们可以解出 $x$
$x=\frac{s-[(n-1)\ast d_1+(n-2)\ast d_2+......+d_{n-1})]}{n}$
又因为 $x$ 是任意整数，我们可以得出来：
$s$ 与 $(n-1)\ast d_1+(n-2)\ast d_2+......+d_{n-1})$ 同余 $n$
这就将题转变成组合问题了，可以用背包的思想去解决！

状态表示：
$f[i][j]$ 选了 $i$ 个 $d$， 余数为 $j$ 的方案数。
状态计算：

• 选 a： $f[i][j]=f[i-1][j-a\ast i]$
• 选 -b：$d[i][j]=f[i-1][j+b\ast i]$
  特别注意： C++数组下标不能取负数，所以我们需要写一个函数，来确保计算出来的数为非负数。

auto getmod = [&](int x)
    {
   
        return (x % n + n) % n;
    };

时间复杂度：$0(n^2)$

AC 代码：

const int mod = 100000007;
const int inf = 2147483647;
const int N = 100009;
int n, s, a, b;
int f[1009][1009];
void solve()
{
   
    cin >> n >> s >> a >> b;
    f[0][0] = 1;
    auto getmod = [&](int x)
    {
   
        return (x % n + n) % n;
    };
    for (int i = 1; i < n; i++)
        for (int j = 0; j < n; j++)
            f[i][j] = (f[i - 1][getmod(j - a * i)] + f[i - 1][getmod(j + b * i)]) % mod;
    
    cout << f[n - 1][getmod(s)] << '\n';
}
int main()
{
   
    buff;
    solve();
}