一、题目描述
二、问题简析
设第一个数为 \(x_0\)，\(d_i=a~or~-b\)，则长度为 \(n\) 的数列的和为：
\[\begin{split} s&=x_0+x_1+x_2+...+x_{n-1}\\ &=(x_0 + 0) + (x_0+d_1) + (x_0+d_1+d_2)+...+(x_0+d_1+...+d_{n-1})\\ &=n*x_0+0+(n-1)*d_1+(n-2)*d_2+...+d_{n-1} \end{split} \]令 \(z_{i}=0+(n-1)*d_1+(n-2)*d_2+...+(n-i)*d_i\)，则 \(s=n*x_0+z_{n-1}\)。
\[\begin{split} &\because s = n * x_0 + z_{n-1} \\ &\therefore x_0=\frac{s-z_{n-1}}{n} \in \mathbb{Z} \\ &\therefore s-z_{n-1} \equiv 0~(\text{mod}~n) \\ &即 s \equiv z_{n-1}~(\text{mod}~n) \end{split} \]设 \(dp[i][j]=\) 使 \(j\equiv z_i(\text{mod}~n)\) 的方案数，则
\[\begin{split} z_i&=z_{i-1}+(n-i)*d_i\\ z_{i-1}&=z_i-(n-i)*d_i\\ z_{i-1} &\equiv z_i-(n-i)*d_i~(\text{mod}~n) \end{split} \]\(d_i\) 可能的值为 \(a\) 或 \(-b\)，
\[z_{i-1}\equiv \begin{cases} z_i-(n-i)*a\\ z_i+(n-i)*b \end{cases} ~(\text{mod}~n) \]至此，我们可以写出递归方程
\[\begin{split} dp[i][j~(\text{mod}~n)] &= dp[i][z_i~(\text{mod}~n)] \\ &=dp[i-1][z_{i-1}~(\text{mod}~n)]~//~包含两种情况\\ &=dp[i-1][z_i-(n-i)*a~(\text{mod}~n)]+dp[i-1][z_i+(n-i)*b~(\text{mod}~n)] \end{split} \]注：
- 1、取模运算可能会产生负数，而数组肯定不能通过负数访问，所以要转化成正数：
(x % n + n) % n。 - 2、
dp[0][0]=1：因为 \(z_0=0\)，算一种情况。
三、AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int quickin(void)
{
int ret = 0;
bool flag = false;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-') flag = true;
ch = getchar();
}
while (ch >= '0' && ch <= '9' && ch != EOF)
{
ret = ret * 10 + ch - '0';
ch = getchar();
}
if (flag) ret = -ret;
return ret;
}
const int MOD = 1e8 + 7;
ll n, s, a, b, dp[1003][1003];
int get_mod(ll x)
{
return (x % n + n) % n;
}
int main()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
#endif
cin >> n >> s >> a >> b;
dp[0][0] = 1;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < n; j++)
{
dp[i][j] = (dp[i - 1][get_mod(j - (n - i) * a)] + dp[i - 1][get_mod(j + (n - i) * b)]) % MOD;
}
}
cout << dp[n - 1][get_mod(s)] << endl;
return 0;
}
完
标签：ch,数列,text,波动,split,equiv,dp,mod From： https://www.cnblogs.com/hoyd/p/18077554