题目描述

关系

内容

观察这个数列：

1 3 0 2 -1 1 -2 …

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

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

输入格式

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

输出格式

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

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

数据范围

$1\le n\le 1000$,
$-{10}^9\le s\le {10}^9$,
$1\le a,b\le {10}^6$

输入样例：

4 10 2 3

输出样例：

2

样例解释

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

问题分析

最初思路

思路分析

这道题是一道组合数学的题目，有难度。现在进行公式推导：

假设首元素为 x，那么长度为 n 的序列可以表示为：

根据题意，该序列的前 n 项和满足：

我们发现 ${\displaystyle x\in Z}$，但是 ${\displaystyle d_i\in \{a,-b\}}$，所以我们可以从 d 入手讨论。对和变形得：

也就是说，右式的值应该模 n 为 0，设 ${\displaystyle w=(n-1)d_1+(n-2)d_2+\cdots +d_{n-1}}$，那么有：

也就是 s 和 w 模 n 同余。从此问题就转化为了求 w 与 s 模 n 同余的数量有多少。

现在可以开始 dp 状态转移的推导了。

状态表示：f[i][j] 表示当前已经选了 i 个 d，前 i 个数的和 w 模 n 的余数为 j 的个数。
状态类型：count
状态划分：

• d[i]==a，那么 f[i][j] = f[i - 1][(j - (n - i) * a) % n]
• d[i]==-b，f[i][j] = f[i - 1][(j + (n - i) * b) % n]
  初始状态：f[0][0] == 1，当我们一个 d 都不选择的时候， w 和 s 自然为 0，也自然是同余的，所以值为 1.

执行流程设计

总结

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1010, MOD = 100000007;
int n, s, a, b;
int f[N][N];

int get(int a, int b) {
    return (a % b + b) % b;
}

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][get(j - (n - i) * a, n)] + f[i - 1][get(j + (n - i) * b, n)]) % MOD;
        }
    }
    
    cout << f[n - 1][get(s, n)];
    return 0;
}