子序列
题目描述
给出一个长度为
n
n
n的序列，你需要计算出所有长度为
k
k
k的子序列中，除最大最小数之外所有数的乘积相乘的结果
输入描述:
第一行一个整数
T
T
T，表示数据组数。
对于每组数据，第一行两个整数
N
N
N，
k
k
k，含义如题所示
接下来一行
N
N
N个整数，表示给出的序列
保证序列内的数互不相同
输出描述:
对于每组数据，输出一个整数表示答案，对
1
0
9
+
7
10^9 + 7
109+7取模
每组数据之间以换行分割
示例1
输入
3
4 3
5 3 1 4
5 4
3 7 5 2 1
10 3
100 1020 2050 102 12 235 4 57 32135 54354
输出
144
81000
521918013
说明
第一组数据解释
所有长度为
3
3
3的子序列为
(
5
,
3
,
1
)
(
5
,
3
,
4
)
(
3
,
1
,
4
)
(
5
,
1
,
4
)
(5, 3, 1) (5, 3, 4) (3, 1, 4) (5, 1, 4)
(5,3,1)(5,3,4)(3,1,4)(5,1,4)
最终答案为
3
∗
4
∗
3
∗
4
=
144
3*4*3*4 =144
3∗4∗3∗4=144
备注:
对于
30
30%
30数据：
T
⩽
10
,
N
⩽
100
,
k
⩽
N
T \leqslant 10, N \leqslant 100, k \leqslant N
T⩽10,N⩽100,k⩽N
对于
60
%
60 \%
60%的数据：
T
⩽
10
,
N
⩽
1000
,
k
⩽
N
T \leqslant 10, N \leqslant 1000, k \leqslant N
T⩽10,N⩽1000,k⩽N
对于
100
%
100 \%
100%的数据：
T
⩽
1000
,
N
⩽
1000
,
k
⩽
N
T \leqslant 1000, N \leqslant 1000, k \leqslant N
T⩽1000,N⩽1000,k⩽N
保证序列中的元素互不相同且
⩽
1
0
6
\leqslant 10^6
⩽106，
k
⩾
3
k \geqslant 3
k⩾3
解决思路：
提示：
1、
a
b
%
m
o
d
a^b\%mod
ab%mod，当
m
o
d
mod
mod是素数时，在计算
b
b
b时一定要对
(
m
o
d
−
1
)
(mod-1)
(mod−1)取模——欧拉降幂。
2、组合数学题，正向不好算时，一定要考虑容斥，别硬卡！！！
已知：见题意。
求解：首先对数排个序，通过枚举可能产生贡献的数计算贡献，存在贡献的数的区间为
[
2
,
n
−
1
]
[2,n-1]
[2,n−1]。
不难想到，计算贡献次数需要用到容斥原理。
对于每个数来说，这个数的贡献次数
=
=
= 所有含这个数的子序列的个数
−
-
− 含这个数并且这个数是子序列的最小值的个数
−
-
− 含这个数并且这个数是子序列的最大值的个数
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
int C[N][N];
int u[N];
ll qpow(ll a, ll b, ll p) {
ll res = 1;
while (b) {
if (b & 1) {
res = res * a % p;
}
a = a * a % p;
b >>= 1;
}
return res;
}
void init(const int n) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0 || i == j) C[i][j] = 1;
else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % (mod - 1);
}
}
}
int main() {
init(1e3);
int T; cin >> T;
while (T--) {
int n, k; scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &u[i]);
sort(u + 1, u + n + 1);
ll ans = 1;
for (int i = 2; i <= n - 1; i++) {
ll t = C[n - 1][k - 1] - C[i - 1][k - 1] - C[n - i][k - 1];
t = (t % (mod - 1) + (mod - 1)) % (mod - 1);
ans = ans * qpow(u[i], t, mod) % mod;
}
printf("%lld\n", ans);
}
return 0;
}
