题目链接
[蓝桥杯 2014 省 A] 波动数列
题目描述
观察这个数列：
1
3
0
2
−
1
1
−
2
…
1\ 3\ 0\ 2\ -1\ 1\ -2\ …
1
3
0
2
−
1
1
−
2
…
这个数列中后一项总是比前一项
增加
2
2
2
或者
减少
3
3
3
，且
每一项都为整数
。
栋栋对这种数列很好奇，他想知道长度为
n
n
n
和为
s
s
s
而且后一项总是比前一项增加
a
a
a
或者减少
b
b
b
的整数数列可能有多少种呢？
输入格式
共一行，包含四个整数
n
,
s
,
a
,
b
n,s,a,b
n
,
s
,
a
,
b
，含义如前面所述。
输出格式
共一行，包含一个整数，表示满足条件的方案数。
由于这个数很大，请输出方案数除以
100000007
100000007
100000007
的余数。
数据范围
-
1
≤
n
≤
1000
1≤n≤1000
1
≤
n
≤
1000
-
−
1
0
9
≤
s
≤
1
0
9
−10^9≤s≤10^9
−
1
0
9
≤
s
≤
1
0
9
-
1
≤
a
,
b
≤
1
0
6
1≤a,b≤10^6
1
≤
a
,
b
≤
1
0
6
输入样例：
4 10 2 3
输出样例：
2
样例解释
两个满足条件的数列分别是
2
4
1
3
2\ 4\ 1\ 3
2
4
1
3
和
7
4
1
−
2
7\ 4\ 1\ -2
7
4
1
−
2
。
解法：同余 + dp
我们可以列出数列的
n
n
n
项，这里假设
x
x
x
是第一项，
d
1
,
d
2
,
.
.
.
,
d
n
−
1
d_1,d_2,...,d_{n-1}
d
1
,
d
2
,
...
,
d
n
−
1
的值为
a
a
a
或者
b
b
b
：
s
=
(
x
)
+
(
x
+
d
1
)
+
(
x
+
d
1
+
d
2
)
+
.
.
.
+
(
x
+
d
1
+
d
2
+
.
.
.
+
d
n
−
1
)
s = (x) + (x + d_1) + (x + d_1 + d_2) + ... + (x + d_1 + d_2 + ... + d_{n - 1})
s
=
(
x
)
+
(
x
+
d
1
)
+
(
x
+
d
1
+
d
2
)
+
...
+
(
x
+
d
1
+
d
2
+
...
+
d
n
−
1
)
将其整理一下可以得到 :
s
=
n
×
x
+
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
.
.
.
+
(
d
n
−
1
)
s = n \times x + (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})
s
=
n
×
x
+
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
...
+
(
d
n
−
1
)
由于
x
x
x
可以是任意的整数，而
s
s
s
是给定的，也就是确定的，于是我们可以通过
s
s
s
得到
x
x
x
：
x
=
s
−
[
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
.
.
.
+
(
d
n
−
1
)
]
n
x =\frac{ s -[ (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})]}{n}
x
=
n
s
−
[(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
...
+
(
d
n
−
1
)]
由于
x
x
x
，也就是数列的第一项，必须是整数。
所以，
n
n
n
必须能够整除
s
−
[
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
.
.
.
+
(
d
n
−
1
)
]
s -[ (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})]
s
−
[(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
...
+
(
d
n
−
1
)]
，也就是
s
−
[
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
.
.
.
+
(
d
n
−
1
)
]
s -[ (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})]
s
−
[(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
...
+
(
d
n
−
1
)]
除以
n
n
n
的余数为
0
0
0
。
我们能够进一步推导出
s
s
s
,
[
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
.
.
.
+
(
d
n
−
1
)
]
[ (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})]
[(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
...
+
(
d
n
−
1
)]
除以
n
n
n
的余数相等，也就是
s
m
o
d
n
≡
[
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
.
.
.
+
(
d
n
−
1
)
]
m
o
d
n
s\ mod\ n \equiv [ (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})] \mod n
s
m
o
d
n
≡
[(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
...
+
(
d
n
−
1
)]
mod
n
，即
s
s
s
,
[
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
.
.
.
+
(
d
n
−
1
)
]
[ (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})]
[(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
...
+
(
d
n
−
1
)]
同余
n
n
n
。
所以我们将原问题转换为：求使得
[
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
.
.
.
+
(
d
n
−
1
)
]
[ (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})]
[(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
...
+
(
d
n
−
1
)]
和
s
s
s
同余
n
n
n
的方案数有多少种。
我们定义
f
[
i
]
[
j
]
f[i][j]
f
[
i
]
[
j
]
为从前
i
i
i
项中选，第
i
i
i
项元素比前一个 增加
a
a
a
或者 减少
b
b
b
，且模
n
n
n
余数是
j
j
j
的方案数。
如果第
i
i
i
项元素选的是
+
a
+a
+
a
：
[
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
.
.
.
+
(
n
−
(
i
−
1
)
)
d
i
−
1
+
(
n
−
1
)
a
]
m
o
d
n
≡
j
[(n - 1)d_1 + (n - 2)d_2 + ... + (n - (i - 1))d_{i - 1} + (n - 1)a] \ mod\ n \equiv j
[(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
...
+
(
n
−
(
i
−
1
))
d
i
−
1
+
(
n
−
1
)
a
]
m
o
d
n
≡
j
将其转换一下：
[
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
.
.
.
+
(
n
−
(
i
−
1
)
)
d
i
−
1
]
m
o
d
n
≡
[
j
−
(
n
−
1
)
a
]
m
o
d
n
[ (n - 1)d_1 + (n - 2)d_2 + ... + (n - (i - 1))d_{i - 1}] \ mod\ n \equiv [j - (n - 1)a] \ mod\ n
[(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
...
+
(
n
−
(
i
−
1
))
d
i
−
1
]
m
o
d
n
≡
[
j
−
(
n
−
1
)
a
]
m
o
d
n
所以我们可以得到
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
−
(
n
−
1
)
a
]
f[i][j] = f[i - 1][j - (n - 1)a]
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
−
(
n
−
1
)
a
]
如果第
i
i
i
项元素选的是
−
b
-b
−
b
：
[
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
.
.
.
+
(
n
−
(
i
−
1
)
)
d
i
−
1
−
(
n
−
1
)
b
]
m
o
d
n
≡
j
[(n - 1)d_1 + (n - 2)d_2 + ... + (n - (i - 1))d_{i - 1} - (n - 1)b] \ mod\ n \equiv j
[(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
...
+
(
n
−
(
i
−
1
))
d
i
−
1
−
(
n
−
1
)
b
]
m
o
d
n
≡
j
将其转换一下：
[
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
.
.
.
+
(
n
−
(
i
−
1
)
)
d
i
−
1
]
m
o
d
n
≡
[
j
+
(
n
−
1
)
b
]
m
o
d
n
[ (n - 1)d_1 + (n - 2)d_2 + ... + (n - (i - 1))d_{i - 1}] \ mod\ n \equiv [j + (n - 1)b] \ mod\ n
[(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
...
+
(
n
−
(
i
−
1
))
d
i
−
1
]
m
o
d
n
≡
[
j
+
(
n
−
1
)
b
]
m
o
d
n
所以我们可以得到
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
+
(
n
−
1
)
b
]
f[i][j] = f[i - 1][j + (n - 1)b]
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
+
(
n
−
1
)
b
]
综上，我们可以得出：
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
+
(
n
−
1
)
b
]
+
f
[
i
−
1
]
[
j
−
(
n
−
1
)
a
]
f[i][j] = f[i - 1][j + (n - 1)b] + f[i - 1][j - (n - 1)a]
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
+
(
n
−
1
)
b
]
+
f
[
i
−
1
]
[
j
−
(
n
−
1
)
a
]
注意：
-
由于
j
−
(
n
−
1
)
a
j - (n - 1)a
j
−
(
n
−
1
)
a
可能小于
0
0
0
，我们必须保证它模
n
n
n
为正数。令
t
=
j
−
(
n
−
1
)
a
t = j - (n - 1)a
t
=
j
−
(
n
−
1
)
a
，那么我们最终得到的余数应该是
(
t
m
o
d
n
+
n
)
m
o
d
n
(t\ mod\ n + n)\ mod\ n
(
t
m
o
d
n
+
n
)
m
o
d
n
，这样就保证了最终的余数是正数。
-
f
[
0
]
[
0
]
f[0][0]
f
[
0
]
[
0
]
应该初始化为
1
1
1
，因为他表示什么也不选也是一种方案，什么也不选那么就只有第一项
x
x
x
。
-
我们最终返回的答案就是
f
[
n
−
1
]
[
(
s
m
o
d
n
+
n
)
m
o
d
n
]
f[n - 1][(s\ mod\ n + n)\ mod\ n]
f
[
n
−
1
]
[(
s
m
o
d
n
+
n
)
m
o
d
n
]
，因为
s
s
s
有可能是负数，所以我们也需要保证它模
n
n
n
是一个正数。
时间复杂度：
O
(
n
2
)
O(n^2)
O
(
n
2
)
C++代码：
#include <iostream>
using namespace std;
const int N = 1010 , MOD = 100000007;
int f[N][N];
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++){
int &val = f[i][j];
val = (val + f[i - 1][get_mod(j - (n - i) * a , n)]) % MOD;
val = (val + f[i - 1][get_mod(j + (n - i) * b , n)]) % MOD;
}
}
cout<<f[n - 1][get_mod(s , n)]<<'\n';
}
Java代码：
import java.io.*;
import java.util.*;
public class Main{
static final int N = 1010 , MOD = 100000007;
static long[][] f = new long[N][N];
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static int get_mod(int a , int b){
return (a % b + b) % b;
}
public static void main(String[] args) throws Exception{
String[] s1 = in.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int s = Integer.parseInt(s1[1]);
int a = Integer.parseInt(s1[2]);
int b = Integer.parseInt(s1[3]);
f[0][0] = 1;
for(int i = 1;i < n;i++){
for(int j = 0;j < n;j++){
f[i][j] = (f[i][j] + f[i - 1][get_mod(j - (n - i) * a , n)]) % MOD;
f[i][j] = (f[i][j] + f[i - 1][get_mod(j + (n - i) * b , n)]) % MOD;
}
}
System.out.println(f[n - 1][get_mod(s,n)]);
}
}
