题干：
题目描述
给出一个长度为n的序列，你需要计算出所有长度为k的子序列中，除最大最小数之外所有数的乘积相乘的结果
输入描述:
第一行一个整数T，表示数据组数。
对于每组数据，第一行两个整数N，k，含义如题所示
接下来一行N个整数，表示给出的序列
保证序列内的数互不相同 输出描述:
对于每组数据，输出一个整数表示答案，对取模
每组数据之间以换行分割
示例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的子序列为
最终答案为
备注:
对于的数据：
对于的数据：
对于的数据：
保证序列中的元素互不相同且， 解题报告：
首先暴力可以n^2。思路就是要算每一个数的贡献，也就是每一个数的出现次数。
总次数是C(n-1,k-1)。我们可以枚举 在前面选了多少个，在后面选了多少个。但是这样复杂度就成了O(nk)了，，也高不了哪去。所以想个办法优化，不难想到，可以求问题的反面，容斥一下，用总次数减去作为最大最小值次数。可以排个序，和前面搭配是作为最大值，和后面搭配作为最小值。
注意，以前组合数是乘数，现在组合数是指数，不要习惯性对p=1e9+7取模。
指数可以对p-1取模。因为这里p是质数，a^(p-1)=1 mod p（费马小定理）
所以，指数减掉若干个p-1，并不影响。
当一般地，(a,p)=1而p不是质数，就欧拉定理，a^(phi(p))=1 mod p所以对phi(p)取模
AC代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;
const int mod=1e9+7;
typedef long long ll;
int n,q,k;
ll a[N];
ll c[N][N];
ll qm(ll x,ll y) {
ll ret=1;
while(y) {
if(y%2==1) ret=(ret*x)%mod;
x=(x*x)%mod;
y/=2;
}
if(ret<0) ret=(ret+mod)%mod;
return ret%mod;
}
signed main() {
for(int i=0; i<=2001; i++) {
c[i][0]=1;
for(int j=1; j<=i; j++) {
c[i][j]=(c[i-1][j-1]+c[i-1][j])%(mod-1);
}
}
scanf("%lld",&q);
while(q--) {
scanf("%lld%lld",&n,&k);
for(int i=1; i<=n; i++)scanf("%lld",&a[i]);
sort(a+1,a+n+1);
ll ans=1;
for(int i=1; i<=n; i++) {
ll ci=(c[n-1][k-1]-c[i-1][k-1]-c[n-i][k-1]+5*(mod-1))%(mod-1);
ans=(ans*qm(a[i],ci))%mod;
}
printf("%lld\n",ans);
}
return 0;
} 参考博客：链接
京公网安备 11010502036488号