波动数列

题目描述

观察这个数列：

1,3,0,2,−1,1,−2

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

输入描述

输入的第一行包含四个整数n,s,a,b,含义如前面所述，其中：

1≤n≤1000,−109≤s≤109,1≤a,b≤106

输出描述

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

解题过程

第一层（10分）

思路

考虑极限情况：

x,x+a,x+2a,x+3a,...x+(n−1)a=nx+n(n−1)2a=sx,x−b,x−2b,x−3b,...x−(n−1)b=nx−n(n−1)2b=s

一式中x为最小值，二式中x为最大值，由此得到x的范围，进而可以枚举每一个x进行DFS

代码

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
using namespace std;
long long n, s, a, b;
long long ans = 0;
const int MOD = 1000000007;

void dfs(int x, int cnt, int sum)
{
	if (cnt == n)
	{
		if (sum == s)
		{
			ans++;
		}
		if (ans > MOD)
		{
			ans %= MOD;
		}
		return;
	}
	dfs(x + a, cnt + 1, sum + x + a);
	dfs(x - b, cnt + 1, sum + x - b);
}

void slove()
{
	long long t = n * (n - 1) / 2;
	long long x;
	long long x1 = s / n - a * (n - 1) / 2;
	long long x2 = 1 + s / n + b * (n - 1) / 2;
	for (int x = x1; x <= x2; x++)
	{
		dfs(x, 1, x);
	}
}

int main()
{
	cin >> n >> s >> a >> b;
	slove();
	cout << ans << endl;
}

第二层（20分）

思路

对枚举数量进行缩减，将a,b一同看为p,原式合并为：

x,x+p,x+2p,x+3p,...x+(n−1)p=nx+n(n−1)2p=s

所以a,b共有n(n−1)2个，选定x,在DFS前枚举a的个数,如果所有a都不能满足nx+taa−(n(n−1)2−ta)b=s，则不进行对此x的DFS。

代码

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
using namespace std;
long long n, s, a, b;
long long ans = 0;
const int MOD = 1000000007;
void dfs(int x, int cnt, int sum)
{
	if (cnt == n)
	{
		if (sum == s)
		{
			ans++;
		}
		if (ans > MOD)
		{
			ans %= MOD;
		}
		return;
	}
	dfs(x + a, cnt + 1, sum + x + a);
	dfs(x - b, cnt + 1, sum + x - b);
}

void slove()
{
	long long t = n * (n - 1) / 2;
	long long x;
	long long x1 = s / n - a * (n - 1) / 2;
	long long x2 = 1 + s / n + b * (n - 1) / 2;
	for (int x = x1; x <= x2; x++)
	{
		for (int cntA = 0; cntA <= t; cntA++)
		{
			long long cal = x * n + cntA * a - (t - cntA) * b;
			if (cal == s)
			{
				dfs(x, 1, x);
			}
		}
	}
}
int Mod(int x,int n) { return (x % n + n) % n; }

int main()
{
	cin >> n >> s >> a >> b;
	slove();
	cout << ans << endl;
}

第三层（100分）

思路

令：

n(n−1)2p=z

原式解出x:

x=s−zn

由于x作为首项，必为整数，所以得到：

s=z(modn)

即s与z同余。
现在我们将p再次转化为f[i]={a,b},原式可写为：

x,x+f[1],x+f[1]+f[2],x+f[1]+f[2]+f[3],...,x+f[1]+...+f[n−1]

合并后为：

nx+(n−1)f[1]+(n−2)f[2]+...+f[n−1]=s

由前面同余的关系，两边取模：

(−f[1]−2f[2]...−f[n−1])%n=s%n

取反：

(f[1]+2f[2]...+f[n−1])%n=(−s)%n

因此我们可以对f[1]-f[n-1]进行动态规划：

dp[i][j]=dp[i][j−i×a]+dp[i][j+i×b]

dp[i][j]表示前i项余数为j的组合数。
最后我们取dp[n-1][(-s)%n]即可得解。

问题产生

取模异常

笔者在查阅题解时发现题解中对于取模并不是直接取模，而是进行了这样的操作：

c++
1
2
3
4
int Mod(int x) 
{ 
    return (x % n + n) % n; 
}

而使用Python3的选手则是像思路那样直接取模。

笔者对此十分的不理解，起初认为是忽略了题目的条件，经过几个小时的查阅笔者找到了这样做的理由：与数学取模保持一致/维护数组下标大于0。

数学取模

定义：如果a和d是两个自然数，d非零，可以证明存在两个唯一的整数q和r，满足a = qd+r 且（0 <= r < d>。其中，q被称为商,r被称为余数。
所以对于（-7）%3,答案应该是2。

但高级语言并不一定为2

C++：cout<<(-7)%3;//输出为-1

Java:System.out.println((-7)%3);//输出为-1

Python:print((-7)%3)//输出为2

结果让我大跌眼镜，查阅资料得知，C++和Java通常会让商大一点，Python通常会让商小一点。所以C++和Java商为-2.Python为-3，进而导致了结果的不同。

所以，为了和我们的认知——数学取模保持一致，我们利用Mod(int x)这个函数让C++的取模和Python和数学取模保持了一致。这也就回答了为什么C++有一种多此一举的感觉。

但是其实，从另一个角度想，就算C++不这样取模，难道答案就会错吗？有没有可能这样做只是为了维护下标大于0？

确实会错

这是在C++下直接取模（下标同+1000）：

错误答案

这是在C++下函数取模：
正确答案

所以，做题还是严格按照数学取模来叭

代码

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

const int N=1e3+3,mod=1e8+7;
int n,dp[N][N];

int Mod(int x){return (x%n+n)%n;}

int main(){
	int s,a,b; scanf("%d%d%d%d",&n,&s,&a,&b);
	dp[0][0]=1;
	for(int i=1;i<n;i++)
		for(int j=0;j<n;j++)
			dp[i][j]=(dp[i-1][Mod(j-a*i)]+dp[i-1][Mod(j+b*i)])%mod;
	printf("%d",dp[n-1][Mod(s)]);
}