[蓝桥杯 2014 省 A] 波动数列

题目描述

观察这个数列：

$1,3,0,2,-1,1,-2, \cdots $。

这个数列中后一项总是比前一项增加 $2$ 或者减少 $3$。

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

输入格式

输入的第一行包含四个整数 $n,s,a,b$，含义如前面说述。

输出格式

输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以 $100000007$ 的余数。

样例 #1

样例输入 #1

4 10 2 3

样例输出 #1

2

提示

【样例说明】

这两个数列分别是 2 4 1 3 和 7 4 1 -2。

【数据规模与约定】

对于 $10\%$ 的数据，$1 \le n \le 5$，$0 \le s \le 5$，$1 \le a,b \le 5$；

对于 $30\%$ 的数据，$1 \le n \le 30$，$0 \le s \le 30$，$1 \le a,b \le 30$；

对于 $50\%$ 的数据，$1 \le n \le 50$，$0 \le s \le 50$，$1 \le a,b \le 50$；

对于 $70\%$ 的数据，$1 \le n \le 100$，$0 \le s \le 500$，$1 \le a,b \le 50$；

对于 $100\%$ 的数据，$1 \le n \le 1000$，$-10^9 \le s \le 10^9$，$1 \le a,b \le 10^6$。

时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛

f[i][j]的状态计算：

分析：首先对于数列x,x+d1,x+d1+d2,x+d1+d2+d3,...,x+d1+d2+d3+...+dn-1这里的d1···dn-1为{+a,-b}

因此数列的和s为nx+(n-1)d1+(n-2)d2+...+dn-1因此就转化为[s-(nx+(n-1)d1+(n-2)d2+···+dn-1)]/n==x,由于x为任意整数即可，所以我们只要保证s和(nx+(n-1)d1+(n-2)d2+···+dn-1)的余数相同即可(同余).

1.当第i个选择a时我们前一个的余数应该为当前余数 在求和中减去该项模n

j%n=j,但是j-a(n-1)%n不一定等于原本的数了我们再次重新取模,记得取正数

2.当我们第i个选择-b时，以上同理。

得到如下转移方程:

f[i][j]=(f[i-1][get_mod(j-a*(n-i),n)]+f[i-1][get_mod(j+b*(n-i),n)])%mod

#include <iostream>
using namespace std;
const int N = 1010, MOD = 100000007;

int f[N][N];
//f[i][j]表示前i项的求和模n等于j的集合(在这样的集合里 有不同的+a -b的排列满足f[i][j])
//属性:count

int get_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][get_mod(j - a * (n - i), n)] + f[i - 1][get_mod(j + b * (n - i), n)]) % MOD;
                      //1.在上一个状态最后面我+a得到当前状态     
                      //  在+a之后 我求和模n等于j 则在+a之前 求和模n等于(j-a(n-i))%n

                      //2.在上一个状态最后面我-b得到当前状态
                      //  且在-b之后 我求和模n等于j 则在-b之前 求和模n等于(j+b(n-i))%n
            //由于 每个d都是未知数 我们要求他的组合,则d的下标也可以反过来 代码更加简洁
            //而且 计算一下也可以知道 n可以省略 毕竟 n%n为0
            f[i][j] = (f[i - 1][get_mod(j - a * i, n)] + f[i - 1][get_mod(j + b * i, n)]) % MOD;

                      //求和的s也可能为负数
    cout << f[n - 1][get_mod(s , n)] << '\n';
    //第一项是后面n - 1组合确定的 故选择 n - 1 个
    return 0;
}