由于数组 $a$ 仅包含 $0$ 和 $1$，对于长度为奇数 $k$ 的子序列，其中位数是 $1$ 的充要条件是：子序列中 $1$ 的个数不少于 $\frac{k+1}{2}$。
因此，求“中位数之和”等价于求“中位数为 $1$的子序列个数”。
思路
代码实现
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
// 定义模数常量，用于所有取模运算
private static final int MOD = 1000000007;
// 定义最大计算范围常量
private static final int MAX_N = 1000001;
// 存储阶乘值的数组
private static long[] fact = new long[MAX_N];
// 存储阶乘逆元的数组
private static long[] invFact = new long[MAX_N];
/**
* 主方法，处理输入输出并计算组合数学问题
*
* @param args 命令行参数
* @throws IOException 可能抛出的IO异常
*/
public static void main(String[] args) throws IOException {
// 使用BufferedReader读取输入，PrintWriter输出结果
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
// 预计算阶乘和逆元，为后续计算做准备
precompute();
// 读取测试用例数量
int T = Integer.parseInt(br.readLine().trim());
// 处理每个测试用例
for (int i = 0; i < T; i++) {
// 读取每行输入并分割，获取n和k的值
String[] str = br.readLine().split("\\s+");
int n = Integer.parseInt(str[0]); // 总数
int k = Integer.parseInt(str[1]); // 选择数
// 统计输入中"1"的数量
int c1 = 0;
String[] strA = br.readLine().split("\\s+");
for (int j = 0; j < n; j++) {
if (strA[j].equals("1")) {
c1++; // 统计"1"的个数
}
}
int c0 = n - c1; // 计算"0"的个数
// 计算至少需要选择的"1"的数量
int m = (k + 1) / 2;
long ans = 0;
// 遍历所有可能的"1"的选择数量
for (int j = m; j <= Math.min(k, c1); j++) {
// 检查剩余的选择数是否不超过"0"的数量
if (k - j <= c0) {
// 计算组合数并累加结果
long res = (nCr(c1, j) * nCr(c0, k - j)) % MOD;
ans = (ans + res) % MOD;
}
}
out.println(ans); // 输出当前测试用例的结果
}
// 清空输出缓冲区并关闭资源
out.flush();
out.close();
br.close();
}
/**
* 使用快速幂算法计算base的exp次方对MOD取模的结果
* 快速幂算法是一种高效计算幂运算的算法，时间复杂度为O(log n)
*
* @param base 底数
* @param exp 指数
* @return base的exp次方对MOD取模的结果
*/
private static long mypower(long base, long exp) {
// 初始化结果为1对MOD取模，防止MOD为1时结果错误
long ans = 1 % MOD;
// 当指数exp大于0时继续循环
while (exp > 0) {
// 如果当前指数是奇数，将base乘入结果
if (exp % 2 == 1) {
ans = (ans * base) % MOD;
}
// base平方，指数减半
base = (base * base) % MOD;
exp /= 2;
}
// 返回最终结果
return ans;
}
/**
* 预计算阶乘和阶乘的逆元数组
* 使用动态规划方法计算阶乘数组fact[]
* 使用费马小定理计算逆元数组invFact[]
*/
private static void precompute() {
// 初始化0的阶乘和0的阶乘逆元为1
fact[0] = 1;
invFact[0] = 1;
// 动态规划计算阶乘数组
for (int i = 1; i < MAX_N; i++) {
fact[i] = (fact[i - 1] * i) % MOD;
}
// 使用费马小定理计算最大阶乘的逆元
invFact[MAX_N - 1] = mypower(fact[MAX_N - 1], MOD - 2);
// 逆向递推计算其他阶乘的逆元
for (int i = MAX_N - 2; i >= 1; i--) {
invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
}
}
/**
* 计算组合数 nCr，即从n个物品中选取r个物品的组合数
* 使用预计算阶乘和阶乘逆元的方法来高效计算组合数
*
* @param n 总物品数
* @param r 选取物品数
* @return 组合数结果，对MOD取模
*/
private static long nCr(int n, int r) {
// 如果r小于0或大于n，组合数为0
if (r < 0 || r > n) {
return 0;
}
// 使用公式 nCr = n! / (r! * (n-r)!) 计算
// 通过预计算的阶乘数组fact和阶乘逆元数组invFact来计算
// 并对MOD取模，防止数值溢出
return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
}
|