AcWing 1214. 波动数列

观察这个数列： $[1, 3, 0, 2, -1,1, -2 \cdots]$ 。

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

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

输入格式

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

输出格式

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

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

数据范围

$1≤n≤1000$ ,
$−10^9≤s≤10^9$ ,
$1≤a,b≤10^6$ .

输入样例：

4 10 2 3

输出样例：

样例解释

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

思路

设数列的第一个数为 $x$ ，则整个数列为 $x,x+d_1,x+d_1+d_2,\cdots,x+\sum\limits_{i=1}^{n-1}d_i$ ，其中 $d_i=a$ 或 $d_i=-b$ 。按照题意，要求 $s=\sum\limits_{i=1}^n\left(x+\sum\limits_{j=1}^{i-1}d_j\right)$ ，即 $s=nx+\sum\limits_{i=1}^{n-1}(n-i)d_i$ ；由于 $x$ 是任意取的，我们可以在模意义下将其消去，即 $s\equiv \sum\limits_{i=1}^{n-1}(n-i)d_i\pmod n$ 。

问题转化成，有一个 $n-1$ 长度的数列，数列中元素的值只可以取 $a$ 或 $-b$ ，数列元素满足 $s\equiv\sum\limits_{i=1}^{n-1}(n-i)d_i\pmod n$ ，问方案数。

设 $f(i,j)$ 表示安排完前 $i$ 个元素， $\sum\limits_{k=1}^{i}(n-k)d_k\equiv j\pmod n$ 的方案数，考虑第 $i+1$ 个元素是什么：若安排 $a$ ，则状态转移到 $f(i+1,[j+(n-i-1)\times a]\bmod n)$ ；若安排 $b$ ，则状态转移到 $f(i+1,[j-(n-i-1)\times b]\bmod n)$ 。

答案为 $f(n-1,s\bmod n)$ 。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: AcWing 1214
Date: 2021 Apr. 5th
Description: Dynamic Programming, Number Theory
*******************************************************************/
#include<iostream>
using namespace std;
typedef long long ll;
const ll MOD = 100000007;
const int MAX_N = 1004;
ll n;
ll s, a, b;
ll f[MAX_N][MAX_N];
ll mod(ll x) {
	return (x % n + n) % n;
}
int main() {
	cin >> n >> s >> a >> b;
	f[0][0] = 1;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n; j++) {
			f[i + 1][mod(j + (n - i - 1) * a)] += f[i][j];
			f[i + 1][mod(j + (n - i - 1) * a)] %= MOD;
			f[i + 1][mod(j - (n - i - 1) * b)] += f[i][j];
			f[i + 1][mod(j - (n - i - 1) * b)] %= MOD;
		}
	}
	cout << f[n - 1][mod(s)] << endl;
	return 0;
}