观察这个数列:
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 ?109≤s≤109
1 ≤ a , b ≤ 1 0 6 1≤a,b≤10^6 1≤a,b≤106
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。
我们可以列出数列的 n n n 项,这里假设 x x x 是第一项, d 1 , d 2 , . . . , d n ? 1 d_1,d_2,...,d_{n-1} d1?,d2?,...,dn?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+d1?)+(x+d1?+d2?)+...+(x+d1?+d2?+...+dn?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)d1?+(n?2)d2?+...+(dn?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=ns?[(n?1)d1?+(n?2)d2?+...+(dn?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)d1?+(n?2)d2?+...+(dn?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)d1?+(n?2)d2?+...+(dn?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)d1?+(n?2)d2?+...+(dn?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?mod?n≡[(n?1)d1?+(n?2)d2?+...+(dn?1?)]modn,即 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)d1?+(n?2)d2?+...+(dn?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)d1?+(n?2)d2?+...+(dn?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)d1?+(n?2)d2?+...+(n?(i?1))di?1?+(n?1)a]?mod?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)d1?+(n?2)d2?+...+(n?(i?1))di?1?]?mod?n≡[j?(n?1)a]?mod?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)d1?+(n?2)d2?+...+(n?(i?1))di?1??(n?1)b]?mod?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)d1?+(n?2)d2?+...+(n?(i?1))di?1?]?mod?n≡[j+(n?1)b]?mod?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]
注意:
时间复杂度: O ( n 2 ) O(n^2) O(n2)
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)]);
}
}