第五届蓝桥杯省赛C++A组 波动序列

一、题意转化

用di代表每一项的加数，会发现其实s是nx+di的后缀和，转化方程后，由于x为整数，可以很容易地得到s与di的后缀和mod n同余，也就是求最终结果为s mod n的后缀和方案数。

二、学到滴东西

同余转化、dp求方案数

三、代码.qaq、

#include
#define rep(i,x,n) for(int i=x;i<=n;i++)

using namespace std;

const int mod=1e8+7;

int n,s,a,b;
int f[1010][1010];
main()
{
    cin >> n >> s >> a >> b;
    
    f[0][0]=1;//求方案首先对初状态初始化为1
    
    rep(i,1,n) rep(j,0,n) 
    f[i][j]=(f[i-1][((j-a*(n-i))%n+n)%n]+f[i-1][((j+b*(n-i))%n+n)%n])%mod;
    //i-1到i的状态转移所有方案
    
    cout << f[n-1][(s%n+n)%n];
}