[Acwing蓝桥杯DP] 1214. 波动数列

题目： 1214. 波动数列 - AcWing题库

题目大意：长度为 n">n 和为 s">s 而且后一项总是比前一项增加 a">a或者减少 b">b 的整数数列可能有多少种

数据范围：    1

                   -10^9

                    1<=a,b<=1e6; 　　

这个题用普通的思维去考虑很难，确实想不到

y总就那么一列 一设变量 一观察 就出来了 真的yyds！

自己确实想一百年也想不到

现将y总的思路总结一下，方便以后复习吧。

设第一个数为x，则第二个数为x+d1，第三个数为x+d1+d2…。这里的d1或d2表示a或者?b

所以这个数列为：  x x+d1 x+d1+d2 .... x+d1+d2...+dn-1

又有已知条件 ： (x)  +  (x+d1) + (x+d1+d2) + ... + (x+d1+d2+dn-1) = s

重点来了： 由于x是初始的值，x可以取任意的整数 范围是相当大的 如果枚举 是不可能的

所以 转化 转化啊  就很神奇 

把 x 提到方程的一边  

为：

 来观察 观察：

发现不用 关注x 只需要 s 除以 n的余数 等于 除以n的余数即可

就是模n相同！amazing！

到这里就转化成了组合问题。

下面就可以用闫氏dp分析法

集合：f [ i ][ j ] 表示：只考虑前 i 个数 且余数是 j 的所有集合的数量

状态计算： 只考虑第i个数 只能取 a 或 -b 。

分析: 第i个数 选择 a 那么 [ ( n - 1 ) * d1 + ( n - 2 ) * d2 + ( n - 3 ) * d3 + ... dn-1  ]% n = j ;  

最后一个第 n项  变量为dn-1 我们已经假设其 为 a 则对应的 系数是 ( n - i );

所以 状态转移方程为：f [ i ] [ j ] = f [ i -1 ][ j - ( n - i) * a] 和f [ i ] [ j ] = f [ i -1 ][ j + ( n - i) * b] 

这样基本就解决了

还有初始化问题 ： 本题初始化非常简单，由于是求方案数

则 初始化 f [ 0 ][ 0 ]=1 不选的时候，余数为0 ，其他的余数均不合法。

代码如下：

#include 

using namespace std;

const int N=1010,MOD=100000007;

int n,s,a,b;
int f[N][N];

int get(int a,int b)//返回 a % b 的正余数
{
    return (a % b + b ) % b;
}

int main()
{
    cin>>n>>s>>a>>b;
    
    f[0][0]=1;
    
    for(int i=1;i)
    {
        for(int j=0;j//枚举余数 余数只能从0~1
        {
            f[i][j]=(f[i-1][get(j-a*(n-i),n)]+f[i-1][get(j+b*(n-i),n)])%MOD;
        }
    }
    
    cout<1][get(s,n)]<<endl;
    
    return 0;
}

end！！！