每日算法打卡：波动数列 day 16

原题链接

1214. 波动数列

题目难度：中等

题目来源：第五届蓝桥杯省赛C++ A组,第五届蓝桥杯省赛Java A组

题目描述

观察这个数列：

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。

题目分析

这道题的意思很简单就是长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种

我们可以从数学角度来看，第一项假设为$x$，第二项就为$x+d_1$，第三项为$x+d_1+d_2$，以此类推，这里的 d i ∈ { + a , ? b } d_i\in\{+a,-b\} di?∈{+a,?b}，然后一共有$n$项

那么他的前n项和为$nx+(n?1)d_1+(n?2)d_2+?+d_{n?1}=s$

我们可以发现在这个过程中的变量是非常多的首先x是属于任意整数的，其次是每一个d，都有两种选法，所以我们可以从后往前进行推算，因为只要后面的数字确定了，前面的情况其实也并不算多

我们可以算出来x

$x=\frac{s?((n?1)d_1+(n?2)d_2+?+d_{n?1})}{n}$

任何一组对应的d的取值都对应了一个x

那么问题就变成了，所有满足要求的d的取值的方案数

第一个要求是每一个d都只能取两种，第二个要求是x必须是整数，即为分子必须是分母的倍数

这里有一个名为同余定理的简化方法，因为需要s减去和与n的模值为0，所以只需要s与和的模n的余数相同即可，因为相减是可以把余数减掉的

那么我们还是使用集合思想的动态规划，对于集合$f(i,j)$，他的含义是前i项的和除n的余数是j的方案数的集合

那么对于状态计算，我们仍然考虑集合划分，可以划分成两个子集，第一种就是最后一项+a的，第二种是最后一项-b的，我们只需要分别求两边的情况方案数相加即可

$f(i?1,(j?i?a)\%n)$

示例代码

#include<iostream>
using namespace std;

const int N = 1010,MOD = 100000007;

int f[N][N];
int mod(int a,int b) // 求正余数
{
    return (a%b+b)%b;
}

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