题目链接
分析
设第一个数为，则第二个数为，第三个数为 ...。这里的，表示或者，所以这个数列为：
, , ,
, ..., ，又因为数列之和为s，所以转化成：
，再在一步转化：
因为x是任意整数，所以又转化成：
与 模的余数相同。
到这里就转化成了组合问题。
下面就可以用闫氏dp分析法了。
1.状态表示：f[i][j]表示要选i个a或者-b且余数为j的所有集合的数量。
2.状态计算：第i个可以选a或者-b。
>第i个选a： 模 。 >
>则： 模 。 >
>系数和下标之和为n，所以第i项的的系数为n-i。
> >所以：f[i][j] = f[i - 1][j - (n - i) * a] >
>第i个选b：同理：f[i][j] = f[i - 1][j + (n - i) * b]
时间复杂度
状态数量 * 状态转移时操作数 = (n - 1) * (n - 1) * 2
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, MOD = 100000007;
int n, s, a, b;
int f[N][N];
int get_mod(int a, int b)
{
return (a % b + b) % b;
}
int main()
{
scanf("%d%d%d%d", &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 - (n - i) * a, n)] + f[i - 1][get_mod(j + (n - i) * b, n)]) % MOD;
printf("%d", f[n - 1][get_mod(s, n)]);
return 0;
}
|
Java代码
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
| import java.util.Scanner;
public class Main {
static int N = 1010;
static int MOD = 100000007;
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n, s, a, b;
n = scan.nextInt();
s = scan.nextInt();
a = scan.nextInt();
b = scan.nextInt();
f[0][0] = 1;
for (int i = 1; i < n; i++)
for (int j = 0; j < n; j++)
f[i][j] = (f[i - 1][getMod(j - (n - i) * a, n)] + f[i - 1][getMod(j + (n - i) * b, n)]) % MOD;
System.out.println(f[n - 1][getMod(s, n)]);
}
public static int getMod(int a, int b) {
return (a % b + b) % b;
}
}
|
参考
ACWing蓝桥杯
